{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Serialize and Deserialize Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #design #string #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #设计 #字符串 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: Codec"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的序列化与反序列化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。</p>\n",
    "\n",
    "<p>请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。</p>\n",
    "\n",
    "<p><strong>提示: </strong>输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 <a href=\"/faq/#binary-tree\">LeetCode 序列化二叉树的格式</a>。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/15/serdeser.jpg\" style=\"width: 442px; height: 324px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,null,null,4,5]\n",
    "<strong>输出：</strong>[1,2,3,null,null,4,5]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2]\n",
    "<strong>输出：</strong>[1,2]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中结点数在范围 <code>[0, 10<sup>4</sup>]</code> 内</li>\n",
    "\t<li><code>-1000 <= Node.val <= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [serialize-and-deserialize-binary-tree](https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [serialize-and-deserialize-binary-tree](https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,null,null,4,5]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        if not root:\n",
    "            return 'None'\n",
    "        root.left = self.serialize(root.left)\n",
    "        root.right = self.serialize(root.right)\n",
    "        return f\"{root.val},{root.left},{root.right}\"\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        dq = deque(data.split(','))\n",
    "\n",
    "        def dfs(li):\n",
    "            val = li.popleft()\n",
    "            if val == \"None\":\n",
    "                return None\n",
    "            root = TreeNode(int(val))\n",
    "            root.left = dfs(li)\n",
    "            root.right = dfs(li)\n",
    "            return root\n",
    "        return dfs(dq)\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        if not root:\n",
    "            return 'None'\n",
    "        root.left = self.serialize(root.left)\n",
    "        root.right = self.serialize(root.right)\n",
    "        return f\"{root.val},{root.left},{root.right}\"\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        dq = deque(data.split(','))\n",
    "\n",
    "        def dfs(li):\n",
    "            val = li.popleft()\n",
    "            if val == \"None\":\n",
    "                return None\n",
    "            root = TreeNode(int(val))\n",
    "            root.left = dfs(li)\n",
    "            root.right = dfs(li)\n",
    "            return root\n",
    "        return dfs(dq)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# class Codec:\n",
    "\n",
    "#     def serialize(self, root):\n",
    "#         if not root: return ''\n",
    "#         queue = deque([root])\n",
    "#         res = []\n",
    "#         while queue:\n",
    "#             node = queue.popleft()\n",
    "#             if node:\n",
    "#                 res.append(str(node.val))\n",
    "#                 queue.append(node.left)\n",
    "#                 queue.append(node.right)\n",
    "#             else:\n",
    "#                 res.append('None')\n",
    "#         return ','.join(res)\n",
    "        \n",
    "\n",
    "#     def deserialize(self, data):\n",
    "#         if not data: return []\n",
    "#         dataList = data.split(',')\n",
    "#         root = TreeNode(int(dataList[0]))\n",
    "#         queue = deque([root])\n",
    "#         i = 1\n",
    "#         while queue:\n",
    "#             node = queue.popleft()\n",
    "#             if dataList[i] != 'None':\n",
    "#                 node.left = TreeNode(int(dataList[i]))\n",
    "#                 queue.append(node.left)\n",
    "#             i += 1\n",
    "#             if dataList[i] != 'None':\n",
    "#                 node.right = TreeNode(int(dataList[i]))\n",
    "#                 queue.append(node.right)\n",
    "#             i += 1\n",
    "#         return root\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        if not root: return 'None'\n",
    "        root.left = self.serialize(root.left)\n",
    "        root.right = self.serialize(root.right)\n",
    "        return f\"{root.val},{root.left},{root.right}\"\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        dataList = data.split(',')\n",
    "        queue = deque(dataList)\n",
    "        def dfs(q):\n",
    "            val = q.popleft()\n",
    "            if val == 'None':\n",
    "                return None\n",
    "            root = TreeNode(int(val))\n",
    "            root.left = dfs(q)\n",
    "            root.right = dfs(q)\n",
    "            return root\n",
    "        return dfs(queue)\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def f(root):\n",
    "            if root==None:\n",
    "                a.append(\"#,\")\n",
    "            else:\n",
    "                a.append(str(root.val)+',')\n",
    "                f(root.left)\n",
    "                f(root.right)\n",
    "        a = []\n",
    "        f(root)\n",
    "        return \"\".join(a)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def g(vals,cnt):\n",
    "            cur = vals[cnt[0]]\n",
    "            cnt[0] += 1\n",
    "            if cur == \"#\":\n",
    "                return \n",
    "            else:\n",
    "                head = TreeNode(int(cur))\n",
    "                head.left = g(vals,cnt)\n",
    "                head.right = g(vals,cnt)\n",
    "            return head\n",
    "\n",
    "\n",
    "        vals = data.split(\",\")\n",
    "        cnt = [0]\n",
    "        return g(vals,cnt)\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    \n",
    "    sep = ','\n",
    "    NULL = '#'\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        if not root:\n",
    "            return ''\n",
    "        \n",
    "        q = [root]\n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            for i in range(sz):\n",
    "                cur = q.pop(0)\n",
    "\n",
    "                if not cur:\n",
    "                    res.append(self.NULL)\n",
    "                    continue\n",
    "                res.append(str(cur.val))\n",
    "\n",
    "                q.append(cur.left)\n",
    "                q.append(cur.right)\n",
    "        \n",
    "\n",
    "        return self.sep.join(res)\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return None\n",
    "        nodes = data.split(self.sep)\n",
    "        root = TreeNode(int(nodes[0]))\n",
    "        q = [root]\n",
    "        i = 1\n",
    "        while i < len(nodes):\n",
    "            node = q.pop(0)\n",
    "            if nodes[i] != self.NULL:\n",
    "                node.left = TreeNode(int(nodes[i]))\n",
    "                q.append(node.left)\n",
    "            i += 1\n",
    "            if i < len(nodes) and nodes[i] != self.NULL:\n",
    "                node.right = TreeNode(int(nodes[i]))\n",
    "                q.append(node.right)\n",
    "            i += 1\n",
    "        return root\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.res = \"\"\n",
    "        self.i = 0\n",
    "\n",
    "    def traversal(self, root):\n",
    "        if not root:\n",
    "            self.res+= \"#,\"     \n",
    "        else:\n",
    "            self.res += str(root.val)+\",\"\n",
    "            self.traversal(root.left)\n",
    "            self.traversal(root.right)\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.traversal(root)\n",
    "        return self.res\n",
    "        \n",
    "    def dfs(self, listOfString):\n",
    "        if listOfString[self.i] == \"#\":\n",
    "            self.i+=1\n",
    "            return None\n",
    "        node = TreeNode(int(listOfString[self.i]))\n",
    "        self.i+=1\n",
    "        node.left = self.dfs(listOfString)\n",
    "        node.right = self.dfs(listOfString)\n",
    "        return node\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        listOfString = data.split(\",\")\n",
    "        return self.dfs(listOfString)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.alist = []\n",
    "        def preorder(root):\n",
    "            if not root:\n",
    "                self.alist.append('#')\n",
    "                return \n",
    "            self.alist.append(str(root.val))\n",
    "            preorder(root.left)\n",
    "            preorder(root.right)\n",
    "        preorder(root)\n",
    "        return ','.join(self.alist)\n",
    "\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        arr = data.split(',')\n",
    "        alen = len(arr)\n",
    "        if alen == 2:return None\n",
    "        return self.buildTree(arr)\n",
    "    \n",
    "    def buildTree(self,arr):\n",
    "        if arr[0] == '#':\n",
    "            arr.pop(0)\n",
    "            return None\n",
    "        root = TreeNode(int(arr[0]))\n",
    "        arr.pop(0)\n",
    "        root.left = self.buildTree(arr)\n",
    "        root.right = self.buildTree(arr)\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def f(root):\n",
    "            if root==None:\n",
    "                a.append(\"#,\")\n",
    "            else:\n",
    "                a.append(str(root.val)+',')\n",
    "                f(root.left)\n",
    "                f(root.right)\n",
    "        a = []\n",
    "        f(root)\n",
    "        return \"\".join(a)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def g(vals,cnt):\n",
    "            \n",
    "            cur = vals[cnt[0]]\n",
    "            cnt[0] += 1\n",
    "            if cur == \"#\":\n",
    "                return\n",
    "            else:\n",
    "                head = TreeNode(int(cur))\n",
    "                head.left = g(vals,cnt)\n",
    "                head.right = g(vals,cnt)\n",
    "            return head\n",
    "        vals = data.split(',')\n",
    "        cnt = [0]\n",
    "        return g(vals,cnt)\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        que = deque([root])\n",
    "        ans = []\n",
    "        while que:\n",
    "            node = que.popleft()\n",
    "            if node:\n",
    "                que.append(node.left)\n",
    "                que.append(node.right)\n",
    "                ans.append(str(node.val))\n",
    "            else:\n",
    "                ans.append('None')\n",
    "        return ','.join(ans)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return []\n",
    "        vallist = data.split(',')\n",
    "        root = TreeNode(int(vallist[0]))\n",
    "        dq = [root]\n",
    "        i = 1\n",
    "        while dq:\n",
    "            if vallist[i] != 'None':\n",
    "                dq[0].left = TreeNode(int(vallist[i]))\n",
    "                dq.append(dq[0].left)\n",
    "            i += 1\n",
    "            if vallist[i] != 'None':\n",
    "                dq[0].right = TreeNode(int(vallist[i]))\n",
    "                dq.append(dq[0].right)\n",
    "            i += 1\n",
    "            dq.pop(0)\n",
    "        return root\n",
    "            \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return self._serialize(root)\n",
    "    \n",
    "    def _serialize(self, node):\n",
    "        if not node:\n",
    "            return \"#\"\n",
    "        left = self._serialize(node.left)\n",
    "        right = self._serialize(node.right)\n",
    "        res = left + \",\" + right + \",\" + str(node.val)\n",
    "        return res\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        nodes = data.split(\",\")\n",
    "        return self._deserialize(nodes)\n",
    "    \n",
    "    def _deserialize(self, nodes):\n",
    "        if not nodes:\n",
    "            return\n",
    "        val = nodes.pop()\n",
    "        if val == \"#\":\n",
    "            return\n",
    "        root = TreeNode(val)\n",
    "        root.right = self._deserialize(nodes)\n",
    "        root.left = self._deserialize(nodes)\n",
    "        return root\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return \"None\"\n",
    "        \n",
    "        return str(root.val) + ',' + self.serialize(root.left) + ',' + self.serialize(root.right)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        dataArray = data.split(',')\n",
    "        self.pos = 0\n",
    "        return self.rdeserialize(dataArray)\n",
    "        \n",
    "    def rdeserialize(self, dataArray: list[str]):\n",
    "        if dataArray[self.pos] == \"None\":\n",
    "            self.pos += 1\n",
    "            return None\n",
    "        \n",
    "        root = TreeNode(int(dataArray[self.pos]))\n",
    "        self.pos += 1\n",
    "        root.left = self.rdeserialize(dataArray)\n",
    "        root.right = self.rdeserialize(dataArray)\n",
    "        \n",
    "        return root\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return 'None'\n",
    "\n",
    "        cur = str(root.val)\n",
    "        l = self.serialize(root.left)\n",
    "        r = self.serialize(root.right)\n",
    "        return cur+','+l+','+r\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        node = data.split(',')\n",
    "        \n",
    "        def dfs():\n",
    "            cur = node.pop(0)\n",
    "            if cur=='None':\n",
    "                return None\n",
    "            root = TreeNode(int(cur))\n",
    "            root.left = dfs()\n",
    "            root.right = dfs()\n",
    "            return root\n",
    "\n",
    "        return dfs()\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        stack = [root]\n",
    "        res = []\n",
    "        while stack:\n",
    "            cur = stack.pop(0)\n",
    "            if cur:\n",
    "                res.append(str(cur.val))\n",
    "                stack.append(cur.left)\n",
    "                stack.append(cur.right)\n",
    "            else:\n",
    "                res.append(\"None\")\n",
    "        return ','.join(res)      \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return []\n",
    "        arr = data.split(',')\n",
    "        root = TreeNode(int(arr[0]))\n",
    "        stack = [root]\n",
    "       \n",
    "        i = 1\n",
    "        while stack:\n",
    "            cur_t = stack.pop(0)\n",
    "           \n",
    "            if arr[i]!='None':\n",
    "                \n",
    "                cur_t.left = TreeNode(arr[i])\n",
    "                stack.append(cur_t.left)\n",
    "            i+=1\n",
    "            if arr[i]!='None':\n",
    "              \n",
    "                cur_t.right = TreeNode(arr[i])\n",
    "                stack.append(cur_t.right)\n",
    "            i+=1\n",
    "        return root\n",
    "                \n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        if root is None:\n",
    "            return ''\n",
    "        res=[]\n",
    "        def preorder(root):\n",
    "            if root is None:\n",
    "                res.append('#,')\n",
    "                return \n",
    "            res.append(str(root.val)+\",\")\n",
    "            preorder(root.left)\n",
    "            preorder(root.right)\n",
    "        preorder(root)\n",
    "        return ''.join(res)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        if not data:\n",
    "            return None\n",
    "        vals = data.split(',')\n",
    "        def inner():\n",
    "            first = vals.pop(0)\n",
    "            if first=='#':\n",
    "                return None\n",
    "            return TreeNode(int(first),inner(),inner())\n",
    "        return inner()\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.NULL = '#'\n",
    "        self.SEQ = ','\n",
    "    \n",
    "    def serialize(self, root):\n",
    "        res = []\n",
    "        self.serialize_(root, res)\n",
    "        return ''.join(res)\n",
    "\n",
    "    def serialize_(self, root, res):\n",
    "        if not root:\n",
    "            res.append(self.NULL)\n",
    "            res.append(self.SEQ)\n",
    "            return\n",
    "        \n",
    "        res.append(str(root.val))\n",
    "        res.append(self.SEQ)\n",
    "\n",
    "        self.serialize_(root.left, res)\n",
    "        self.serialize_(root.right, res)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        nodes = data.split(self.SEQ)\n",
    "        return self.deserialize_(nodes)\n",
    "    \n",
    "    def deserialize_(self, nodes):\n",
    "        if not nodes:\n",
    "            return None\n",
    "        root_val = nodes.pop(0)\n",
    "        if root_val == self.NULL:\n",
    "            return None\n",
    "        root = TreeNode(root_val)\n",
    "        root.left = self.deserialize_(nodes)\n",
    "        root.right = self.deserialize_(nodes)\n",
    "\n",
    "        return root\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from collections import deque\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        queue = deque([root])\n",
    "        res = []\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else:\n",
    "                res.append('')\n",
    "        return ','.join(res)\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return None\n",
    "        data = data.split(',')\n",
    "\n",
    "        root = TreeNode(int(data[0]))\n",
    "        queue = deque([root])\n",
    "        i = 1\n",
    "        while i < len(data):\n",
    "            node = queue.popleft()\n",
    "            val = data[i]\n",
    "            if val:\n",
    "                newNode = TreeNode(int(val))\n",
    "                node.left = newNode\n",
    "                queue.append(newNode)\n",
    "            i += 1\n",
    "\n",
    "            val = data[i]\n",
    "            if val:\n",
    "                newNode = TreeNode(int(val))\n",
    "                node.right = newNode\n",
    "                queue.append(newNode)\n",
    "            i += 1\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def dfs(node):\n",
    "            if node==None:\n",
    "                preorder.append('null')\n",
    "                return\n",
    "            preorder.append(str(node.val))\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        preorder = []\n",
    "        dfs(root)\n",
    "        return ','.join(preorder)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        preorder = data.split(',')\n",
    "        # preorder = collections.deque(preorder)\n",
    "        def dfs():\n",
    "            # if len(preorder)==0:\n",
    "            #     return\n",
    "            val = preorder.pop(0)\n",
    "            if val=='null':\n",
    "                return None\n",
    "            node = TreeNode(val)\n",
    "            node.left = dfs()\n",
    "            node.right = dfs()\n",
    "            return node\n",
    "        return dfs()\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        q = []\n",
    "        res = []\n",
    "        if not root:\n",
    "            return res\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            curr = q.pop(0)\n",
    "            \n",
    "            if curr != None:\n",
    "                res.append(str(curr.val))\n",
    "                q.append(curr.left)\n",
    "                q.append(curr.right)\n",
    "            else:\n",
    "                res.append('None')\n",
    "        return ','.join(res)\n",
    "                \n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return []\n",
    "        q = []\n",
    "        datal = data.split(',')\n",
    "        root = TreeNode(datal[0])\n",
    "        q.append(root)\n",
    "        idx = 1\n",
    "        while q:\n",
    "            curr = q.pop(0)\n",
    "            if datal[idx] != 'None':\n",
    "                curr.left = TreeNode(datal[idx])\n",
    "                q.append(curr.left)\n",
    "            idx += 1\n",
    "            if datal[idx] != 'None':\n",
    "                curr.right = TreeNode(datal[idx])\n",
    "                q.append(curr.right)\n",
    "            idx += 1\n",
    "        \n",
    "        return root\n",
    "            \n",
    "                \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return ''\n",
    "        stack = [root]\n",
    "        res = []\n",
    "        while stack:\n",
    "            tmp = []\n",
    "            for s in stack:\n",
    "                if not s:\n",
    "                    res.extend(['#'])\n",
    "                else:\n",
    "                    res.append(str(s.val))\n",
    "                    tmp.extend([s.left, s.right])\n",
    "            stack = tmp\n",
    "        return ','.join(res)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == '':\n",
    "            return None\n",
    "        data = data.split(',')\n",
    "        root = TreeNode(int(data[0]))\n",
    "        stack = [root]\n",
    "        length = len(data)\n",
    "        cur = 0\n",
    "        for i in range(1, length):\n",
    "            if i % 2 == 1:\n",
    "                cur = stack.pop(0)\n",
    "            if i % 2 == 1 and data[i] != '#':\n",
    "                cur.left = TreeNode(int(data[i]))\n",
    "                stack.append(cur.left)\n",
    "            elif i % 2 == 0 and data[i] != '#':\n",
    "                cur.right = TreeNode(int(data[i]))\n",
    "                stack.append(cur.right)\n",
    "        return root \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        q = []\n",
    "        res = []\n",
    "        if not root:\n",
    "            return res\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            curr = q.pop(0)\n",
    "            \n",
    "            if curr != None:\n",
    "                res.append(curr.val)\n",
    "                q.append(curr.left)\n",
    "                q.append(curr.right)\n",
    "            else:\n",
    "                res.append('None')\n",
    "        return res\n",
    "                \n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return []\n",
    "        q = []\n",
    "        root = TreeNode(data[0])\n",
    "        q.append(root)\n",
    "        idx = 1\n",
    "        while q:\n",
    "            curr = q.pop(0)\n",
    "            if data[idx] != 'None':\n",
    "                curr.left = TreeNode(data[idx])\n",
    "                q.append(curr.left)\n",
    "            idx += 1\n",
    "            if data[idx] != 'None':\n",
    "                curr.right = TreeNode(data[idx])\n",
    "                q.append(curr.right)\n",
    "            idx += 1\n",
    "        \n",
    "        return root\n",
    "            \n",
    "                \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        dq = deque([root])\n",
    "        res = []\n",
    "        while dq:\n",
    "            node = dq.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                dq.append(node.left)\n",
    "                dq.append(node.right)\n",
    "            else:\n",
    "                res.append('None')\n",
    "        return ','.join(res)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        if not data:\n",
    "            return []\n",
    "        dataList = data.split(',')\n",
    "        root = TreeNode(int(dataList[0]))\n",
    "        dq = deque([root])\n",
    "        i = 1\n",
    "        while dq:\n",
    "            node = dq.popleft()\n",
    "            if dataList[i] != 'None':\n",
    "                node.left = TreeNode(int(dataList[i]))\n",
    "                dq.append(node.left)\n",
    "            i += 1\n",
    "            if dataList[i] != 'None':\n",
    "                node.right = TreeNode(int(dataList[i]))\n",
    "                dq.append(node.right)\n",
    "            i += 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return ''\n",
    "        \n",
    "        queue = []\n",
    "        rst = []\n",
    "        queue.append(root)\n",
    "\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if not node:\n",
    "                rst.append('#')\n",
    "            else:\n",
    "                rst.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "        \n",
    "        return ','.join(rst)\n",
    "            \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        \n",
    "        if data == '':\n",
    "            return None\n",
    "        \n",
    "        chars = data.split(',')\n",
    "        root = TreeNode(chars[0])\n",
    "        queue = []\n",
    "        queue.append(root)\n",
    "\n",
    "        i = 0\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            # 左            \n",
    "            i = i + 1\n",
    "            if chars[i] == '#':\n",
    "                node.left = None\n",
    "            else:\n",
    "                node.left = TreeNode(chars[i])\n",
    "                queue.append(node.left)\n",
    "        \n",
    "            # 右\n",
    "            i = i + 1\n",
    "            if chars[i] == '#':\n",
    "                node.right = None\n",
    "            else:\n",
    "                node.right = TreeNode(chars[i])\n",
    "                queue.append(node.right)\n",
    "\n",
    "        \n",
    "        return root\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"#\"\n",
    "        res=str(root.val)\n",
    "        res+=\",\"+self.serialize(root.left)\n",
    "        res+=\",\"+self.serialize(root.right)\n",
    "        return res\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        data=data.split(\",\")\n",
    "        data=data[::-1]\n",
    "        def construct(data):\n",
    "            if not data:\n",
    "                return None\n",
    "            tmp=data.pop()\n",
    "            if tmp==\"#\":\n",
    "                return None\n",
    "            root=TreeNode(int(tmp))\n",
    "            root.left=construct(data)\n",
    "            root.right=construct(data)\n",
    "\n",
    "            return root  \n",
    "\n",
    "        return construct(data)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: strr\n",
    "        \"\"\"\n",
    "        res = \"\"\n",
    "        if (not root):\n",
    "            res += \"N,\"\n",
    "            # print (res)\n",
    "            return res\n",
    "\n",
    "        res += str(root.val) + ','\n",
    "        res += self.serialize(root.left)\n",
    "        res += self.serialize(root.right)\n",
    "        # print (res)\n",
    "        return res\n",
    "        \n",
    "    def subdeserialize(self, vals):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type vals: List(char) \n",
    "        :rtype: TreeNode\n",
    "        \"\"\"   \n",
    "        # print (vals)\n",
    "\n",
    "        cur = vals.pop(0)\n",
    "        if (cur == 'N'):\n",
    "            return None\n",
    "\n",
    "        root = TreeNode(int(cur))\n",
    "        root.left = self.subdeserialize(vals)\n",
    "        root.right = self.subdeserialize(vals)\n",
    "\n",
    "        return root\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        vals = data.split(\",\")\n",
    "        # print (vals)\n",
    "        return self.subdeserialize(vals[:-1])\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        self.res = []\n",
    "        if not root:\n",
    "            return ''\n",
    "            \n",
    "        q = collections.deque()\n",
    "        q.append(root)\n",
    "        # 从上到下遍历二叉树的每一层\n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            # 从左到右遍历每一层的每个节点\n",
    "            for i in range(sz):\n",
    "                cur = q.popleft()\n",
    "                if cur:\n",
    "                    self.res.append(str(cur.val))\n",
    "                    q.append(cur.left)\n",
    "                    q.append(cur.right)\n",
    "                else:\n",
    "                    self.res.append(\"null\")\n",
    "\n",
    "        self.res = ','.join(self.res)\n",
    "        return self.res\n",
    "    \n",
    "    def deserialize(self, data):\n",
    "        if data == '': \n",
    "            return None\n",
    "        vals, i = data.split(','), 1\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if vals[i] != \"null\":\n",
    "                node.left = TreeNode(int(vals[i]))\n",
    "                queue.append(node.left)\n",
    "            i += 1\n",
    "            if vals[i] != \"null\":\n",
    "                node.right = TreeNode(int(vals[i]))\n",
    "                queue.append(node.right)\n",
    "            i += 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from collections import deque\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        ret=[]\n",
    "        dq=deque([root])\n",
    "        while dq:\n",
    "            node=dq.popleft()\n",
    "            if node:\n",
    "                ret.append(str(node.val))\n",
    "                dq.append(node.left)\n",
    "                dq.append(node.right)\n",
    "            else:\n",
    "                ret.append('None')\n",
    "        return ','.join(ret)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return []\n",
    "        datalist=data.split(',')\n",
    "        root=TreeNode(int(datalist[0]))\n",
    "        dq=deque([root])\n",
    "        i=1\n",
    "        while dq:\n",
    "            node=dq.popleft()\n",
    "            if datalist[i] != 'None':\n",
    "                node.left = TreeNode(int(datalist[i]))\n",
    "                dq.append(node.left)\n",
    "            i+=1\n",
    "            if datalist[i] != 'None':\n",
    "                node.right = TreeNode(int(datalist[i]))\n",
    "                dq.append(node.right)\n",
    "            i+=1\n",
    "        return root\n",
    "            \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from collections import deque\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        q = deque([root])\n",
    "        res = []\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            \n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                q.append(node.left)\n",
    "                q.append(node.right)\n",
    "            else:\n",
    "                res.append('None')\n",
    "        return \",\".join(res)\n",
    "\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return []\n",
    "        data_list = data.split(',')\n",
    "\n",
    "        root = TreeNode(int(data_list[0]))\n",
    "        i = 1\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if data_list[i]!='None':\n",
    "                left_node = TreeNode(int(data_list[i]))\n",
    "                node.left = left_node\n",
    "                q.append(left_node)\n",
    "            i+=1\n",
    "            if data_list[i]!='None':\n",
    "                right_node = TreeNode(int(data_list[i]))\n",
    "                node.right = right_node\n",
    "                q.append(right_node)\n",
    "            i += 1\n",
    "        return root\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root: return \"[]\"\n",
    "        res = []\n",
    "        queue = collections.deque([root])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "\n",
    "            else:\n",
    "                res.append(\"null\")\n",
    "\n",
    "        return \"[\" + \",\".join(res) + \"]\"\n",
    "\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == \"[]\": return\n",
    "        data = data[1:-1].split(\",\")\n",
    "        root = TreeNode(int(data[0]))\n",
    "        idx = 1\n",
    "        queue = collections.deque([root])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if data[idx] != \"null\":\n",
    "                node.left = TreeNode(int(data[idx]))\n",
    "                queue.append(node.left)\n",
    "            idx += 1\n",
    "            if data[idx] != \"null\":\n",
    "                node.right = TreeNode(int(data[idx]))\n",
    "                queue.append(node.right)\n",
    "            idx += 1\n",
    "        \n",
    "        return root\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        deque = [root]\n",
    "        while deque:\n",
    "            node = deque.pop(0)\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                deque.append(node.left)\n",
    "                deque.append(node.right)\n",
    "            else:\n",
    "                 res.append('None')\n",
    "        return ','.join(res)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return []\n",
    "        data = data.split(',')\n",
    "        root = TreeNode(int(data[0]))\n",
    "        dp = [root]\n",
    "        if len(data) == 1:\n",
    "            return root\n",
    "        i = 1\n",
    "        while dp:\n",
    "            node = dp.pop(0)\n",
    "            if data[i] != 'None':\n",
    "                node.left = TreeNode(int(data[i]))\n",
    "                dp.append(node.left)\n",
    "            i += 1\n",
    "            if data[i] != 'None':\n",
    "                node.right = TreeNode(int(data[i]))\n",
    "                dp.append(node.right)\n",
    "            i += 1\n",
    "        return root\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.SEP = ','\n",
    "        self.NULL = '#'\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        sb = []\n",
    "        self._serialize(root, sb)\n",
    "        return ''.join(sb)\n",
    "    def _serialize(self, root, sb):\n",
    "        if not root:\n",
    "            sb.append(self.NULL)\n",
    "            sb.append(self.SEP)\n",
    "            return\n",
    "        sb.append(str(root.val))\n",
    "        sb.append(self.SEP)\n",
    "        self._serialize(root.left,sb)\n",
    "        self._serialize(root.right,sb)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        nodes = data.split(self.SEP)\n",
    "        return self._deserialize(nodes)\n",
    "        \n",
    "    def _deserialize(self, nodes):\n",
    "        if not nodes:\n",
    "            return None\n",
    "        val = nodes.pop(0)\n",
    "        if val == self.NULL:\n",
    "            return None\n",
    "        root = TreeNode(val)\n",
    "        root.left = self._deserialize(nodes)\n",
    "        root.right = self._deserialize(nodes)\n",
    "        return root\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"#\"\n",
    "        self.s = \"\"\n",
    "        self.serializeFunction(root)\n",
    "        return self.s\n",
    "    def serializeFunction(self, root):\n",
    "        if not root:\n",
    "            self.s += \"#\"\n",
    "            return \n",
    "        \n",
    "        self.s += str(root.val) + \"!\"\n",
    "        self.serializeFunction(root.left)\n",
    "        self.serializeFunction(root.right) \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        self.index = 0\n",
    "        if data == \"#\":\n",
    "            return None\n",
    "        return self.deserializeFunction(data)\n",
    "\n",
    "    def deserializeFunction(self, data):\n",
    "        if self.index >= len(data) or data[self.index]==\"#\":\n",
    "            self.index += 1 # 跳过#号\n",
    "            return None\n",
    "        \n",
    "        val = 0\n",
    "        flag = False\n",
    "        while self.index < len(data) and data[self.index]!=\"!\":\n",
    "            if data[self.index] == \"-\":\n",
    "                flag = True\n",
    "            else:\n",
    "                val = val *10 + int(data[self.index])\n",
    "            self.index += 1\n",
    "        if flag:\n",
    "            val = (-1)*val \n",
    "        root = TreeNode(val)\n",
    "        \n",
    "        # 跳过分割的感叹号\n",
    "        if self.index == len(data):\n",
    "            return root\n",
    "        else:\n",
    "            self.index += 1\n",
    "\n",
    "        root.left = self.deserializeFunction(data)\n",
    "        root.right = self.deserializeFunction(data)\n",
    "\n",
    "        return root\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root: return []\n",
    "        res = []\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            cur_level_length = len(queue)\n",
    "            for _ in range(cur_level_length):\n",
    "                node = queue.popleft()\n",
    "                # 额外增加空值\n",
    "                if not node:\n",
    "                    res.append(None)\n",
    "                    continue\n",
    "                res.append(node.val)\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "        \n",
    "        return res\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data: return None\n",
    "    \n",
    "        index = 0\n",
    "        val = data[index]\n",
    "        root = TreeNode(val)\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            # 左节点\n",
    "            if data[2 * index + 1] is not None:\n",
    "                node.left = TreeNode(data[2 * index + 1])\n",
    "                queue.append(node.left)\n",
    "            if data[2 * index + 2] is not None:\n",
    "                node.right = TreeNode(data[2 * index + 2])\n",
    "                queue.append(node.right)\n",
    "            \n",
    "            index += 1\n",
    "\n",
    "        return root\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        ans = \"\"\n",
    "        def recurse(root):\n",
    "            nonlocal ans\n",
    "            if root == None:\n",
    "                ans += \",\" + \"None\"\n",
    "                return\n",
    "            ans += \",\" + str(root.val)\n",
    "            recurse(root.left)\n",
    "            recurse(root.right)\n",
    "        recurse(root)\n",
    "        return ans[1:]\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        load = deque(data.split(','))\n",
    "        \n",
    "        def dfs(load):\n",
    "            v = load.popleft()\n",
    "            if v == 'None':\n",
    "                return None\n",
    "            root = TreeNode(int(v))\n",
    "            root.left = dfs(load)\n",
    "            root.right = dfs(load)\n",
    "            return root\n",
    "        return dfs(load)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root: Optional[TreeNode]) -> str:\n",
    "        ans = []\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if not node:\n",
    "                ans.append('x')\n",
    "                continue\n",
    "            ans.append(str(node.val))\n",
    "            q.append(node.left)\n",
    "            q.append(node.right)\n",
    "        return ','.join(ans)\n",
    "\n",
    "    def deserialize(self, data: str) -> Optional[TreeNode]:\n",
    "        vals = data.split(',')\n",
    "        if vals[0] == 'x':\n",
    "            return None\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        q = deque([root])\n",
    "        for i in range(1, len(vals), 2):\n",
    "            lv, rv = vals[i], vals[i+1]\n",
    "            node = q.popleft()\n",
    "            if lv != 'x':\n",
    "                lchild = TreeNode(int(lv))\n",
    "                node.left = lchild\n",
    "                q.append(lchild)\n",
    "            if rv != 'x':\n",
    "                rchild = TreeNode(int(rv))\n",
    "                node.right = rchild\n",
    "                q.append(rchild)\n",
    "        return root\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import queue\n",
    "\n",
    "\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        q = queue.Queue()\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        q.put(root)\n",
    "        result = \"\"\n",
    "\n",
    "        while not q.empty():\n",
    "            # print(q.queue)\n",
    "            curnode = q.get()\n",
    "\n",
    "            if result!=\"\":\n",
    "                result += \",\"\n",
    "            if not curnode:\n",
    "                result += \"None\"\n",
    "            else:\n",
    "                result += str(curnode.val)\n",
    "                q.put(curnode.left)\n",
    "                q.put(curnode.right)\n",
    "        return result\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "\n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        l = data.split(\",\")\n",
    "        print(l)\n",
    "        q = queue.Queue()\n",
    "\n",
    "        if len(l)==1:\n",
    "            return None\n",
    "        root = TreeNode(int(l[0]))\n",
    "        q.put(root)\n",
    "\n",
    "        num = 1\n",
    "        while not q.empty():\n",
    "            curnode = q.get()\n",
    "            if curnode:\n",
    "                curnode.left = TreeNode(int(l[num])) if l[num]!=\"None\" else None\n",
    "                q.put(curnode.left)\n",
    "                curnode.right = TreeNode(int(l[num+1])) if l[num+1]!=\"None\" else None\n",
    "                q.put(curnode.right)\n",
    "                num += 2\n",
    "        return root\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from queue import Queue\n",
    "\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    none_node_flag = \"#\"\n",
    "\n",
    "    def serialize(self, root: TreeNode):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        path = []\n",
    "\n",
    "        def dfs(node: TreeNode):\n",
    "            if not node:\n",
    "                path.append(self.none_node_flag)\n",
    "                return\n",
    "            path.append(str(node.val))\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return \",\".join(path)\n",
    "\n",
    "    def deserialize(self, data: str):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        q = Queue()\n",
    "        for val in data.split(\",\"):\n",
    "            q.put(val)\n",
    "\n",
    "        def build() -> Optional[TreeNode]:\n",
    "            if q.qsize() == 0:\n",
    "                return None\n",
    "            val = q.get()\n",
    "            if val == self.none_node_flag:\n",
    "                return None\n",
    "            node = TreeNode(val)\n",
    "            node.left = build()\n",
    "            node.right = build()\n",
    "            return node\n",
    "        return build()\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import json\n",
    "\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return json.dumps(self.serialize_impl(root))\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return self.deserialize_impl(json.loads(data))\n",
    "\n",
    "    def serialize_impl(self, root: TreeNode) -> List:\n",
    "        if root is None:\n",
    "            return []\n",
    "        vals = [root.val]\n",
    "        if root.left is not None:\n",
    "            vals.append(self.serialize_impl(root.left))\n",
    "        elif root.right is not None:\n",
    "            vals.append(None)\n",
    "        if root.right is not None:\n",
    "            vals.append(self.serialize_impl(root.right))\n",
    "        return vals\n",
    "\n",
    "    def deserialize_impl(self, vals: List) -> TreeNode:\n",
    "        if vals is None or len(vals) == 0:\n",
    "            return None\n",
    "        root = TreeNode(vals[0])\n",
    "        if len(vals) >= 2:\n",
    "            root.left = self.deserialize_impl(vals[1])\n",
    "        if len(vals) >= 3:\n",
    "            root.right = self.deserialize_impl(vals[2])\n",
    "        return root\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 'None'\n",
    "        return str(root.val) + ',' + self.serialize(root.left) + ',' + self.serialize(root.right)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def dfs(datalist):\n",
    "            val = datalist.popleft()\n",
    "            if val == 'None':\n",
    "                return None\n",
    "            root = TreeNode(val)\n",
    "            root.left = dfs(datalist)\n",
    "            root.right = dfs(datalist)\n",
    "            return root\n",
    "        \n",
    "        datalist = collections.deque(data.split(','))\n",
    "        return dfs(datalist)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        #前序遍历\n",
    "        if not root: return \"[]\"\n",
    "        queue = collections.deque()\n",
    "        res = []\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            ans = []\n",
    "            for i in range(n):\n",
    "                node = queue.popleft()\n",
    "                if node:\n",
    "                    res.append(str(node.val))\n",
    "                    ans.append(node.left)\n",
    "                    ans.append(node.right)\n",
    "                else:\n",
    "                    res.append(str(None))\n",
    "            queue.extend(ans)\n",
    "        self.serialized_data = \"#\".join(res)         \n",
    "        # print(self.serialized_data)\n",
    "        return self.serialized_data\n",
    "            \n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == \"[]\": return \n",
    "        da = data.split('#')\n",
    "        root = TreeNode(int(da[0]))\n",
    "        tree_queue = collections.deque()\n",
    "        tree_queue.append(root)\n",
    "        i = 1\n",
    "        while tree_queue:\n",
    "            node = tree_queue.popleft()\n",
    "            if da[i] != \"None\":\n",
    "                node.left = TreeNode(int(da[i]))\n",
    "                tree_queue.append(node.left)\n",
    "            i += 1\n",
    "            if da[i] != \"None\":\n",
    "                node.right = TreeNode(int(da[i]))\n",
    "                tree_queue.append(node.right)\n",
    "            i += 1\n",
    "        return root \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        queue = deque([root])\n",
    "        res=\"\"\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res=res+str(node.val)+'_'\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else:\n",
    "                res=res+\"None_\"\n",
    "        print(res)\n",
    "        return res[:-1]\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return None\n",
    "        datalist = data.split('_')\n",
    "        root = TreeNode(datalist[0])\n",
    "        queue = deque([root])\n",
    "        i = 1\n",
    "        print(datalist)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if datalist[i] != 'None':\n",
    "                left=TreeNode(int(datalist[i]))\n",
    "                node.left=left\n",
    "                queue.append(left)\n",
    "            i+=1\n",
    "            if datalist[i] != 'None':\n",
    "                right=TreeNode(int(datalist[i]))\n",
    "                node.right=right\n",
    "                queue.append(right)\n",
    "            i+=1\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root: return \"[]\"\n",
    "        res = []\n",
    "        queue = collections.deque([root])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "\n",
    "            else:\n",
    "                res.append(\"null\")\n",
    "\n",
    "        return \"[\" + \",\".join(res) + \"]\"\n",
    "\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == \"[]\": return None\n",
    "        data = data[1:-1].split(\",\")\n",
    "        idx = 1\n",
    "        root = TreeNode(int(data[0]))\n",
    "        queue = collections.deque([root])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if data[idx] != \"null\":\n",
    "                node.left = TreeNode(int(data[idx]))\n",
    "                queue.append(node.left)\n",
    "            idx += 1\n",
    "            if data[idx] != \"null\":\n",
    "                node.right = TreeNode(int(data[idx]))\n",
    "                queue.append(node.right)\n",
    "            idx += 1\n",
    "\n",
    "            if idx >= len(data): break\n",
    "        \n",
    "        return root\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return '#'\n",
    "        leftstr = self.serialize(root.left)\n",
    "        rightstr = self.serialize(root.right)\n",
    "        return str(root.val) + ',' + leftstr + ',' + rightstr\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        lser = data.split(',')\n",
    "        self.i = 0\n",
    "        return self.dfs(lser)\n",
    "\n",
    "    def dfs(self, liststr):\n",
    "        s = liststr[self.i]\n",
    "        self.i += 1\n",
    "        if s == '#':\n",
    "            return None\n",
    "        node = TreeNode(int(s))\n",
    "        node.left = self.dfs(liststr)\n",
    "        node.right = self.dfs(liststr)\n",
    "        return node\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return '#'\n",
    "        return str(root.val) + ' ' + self.serialize(root.left) + ' ' + self.serialize(root.right)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "\n",
    "        def dfs(strs):\n",
    "            v = strs.pop(0)\n",
    "            if v == '#':\n",
    "                return None\n",
    "            \n",
    "            node = TreeNode(v)\n",
    "            node.left = dfs(strs)\n",
    "            node.right = dfs(strs)\n",
    "            return node\n",
    "\n",
    "        strs = data.split(' ')\n",
    "        return dfs(strs)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        queue = deque([root])\n",
    "        res=\"\"\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res=res+str(node.val)+'_'\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else:\n",
    "                res=res+\"None_\"\n",
    "        \n",
    "        return res[:-1]\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return None\n",
    "        datalist = data.split('_')\n",
    "        root = TreeNode(datalist[0])\n",
    "        queue = deque([root])\n",
    "        i = 1\n",
    "        \n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if datalist[i] != 'None':\n",
    "                left=TreeNode(int(datalist[i]))\n",
    "                node.left=left\n",
    "                queue.append(left)\n",
    "            i+=1\n",
    "            if datalist[i] != 'None':\n",
    "                right=TreeNode(int(datalist[i]))\n",
    "                node.right=right\n",
    "                queue.append(right)\n",
    "            i+=1\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"[]\"\n",
    "        queue = []\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else:\n",
    "                res.append(\"null\")\n",
    "        return \"[\" + \",\".join(res) + \"]\"\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == \"[]\":\n",
    "            return None \n",
    "        vals = data[1:-1].split(\",\")\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        queue = []\n",
    "        queue.append(root)\n",
    "\n",
    "        idx = 1\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if vals[idx] != \"null\":\n",
    "                node.left = TreeNode(int(vals[idx]))\n",
    "                queue.append(node.left)\n",
    "            idx += 1\n",
    "            if vals[idx] != \"null\":\n",
    "                node.right = TreeNode(int(vals[idx]))\n",
    "                queue.append(node.right)\n",
    "            idx += 1\n",
    "        return root \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.res = []\n",
    "        def traverse(root):\n",
    "            if root is None:\n",
    "                self.res.append(\"*\")\n",
    "                return\n",
    "            \n",
    "            self.res.append(str(root.val))\n",
    "            traverse(root.left)\n",
    "            traverse(root.right)\n",
    "        traverse(root)\n",
    "        return \",\".join(self.res)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        res = data.split(',')\n",
    "        print(res)\n",
    "        def build(res):\n",
    "            root_val = res.pop(0)\n",
    "            if root_val == \"*\":\n",
    "                return None\n",
    "            \n",
    "            root = TreeNode(int(root_val))\n",
    "            \n",
    "            root.left = build(res)\n",
    "            root.right = build(res)\n",
    "            return root\n",
    "        \n",
    "        return build(res)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        if not root: return ''\n",
    "        queue = deque([root])\n",
    "        res = []\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else:\n",
    "                res.append('None')\n",
    "        return ','.join(res)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        if not data: return []\n",
    "        dataList = data.split(',')\n",
    "        root = TreeNode(int(dataList[0]))\n",
    "        queue = deque([root])\n",
    "        i = 1\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if dataList[i] != 'None':\n",
    "                node.left = TreeNode(int(dataList[i]))\n",
    "                queue.append(node.left)\n",
    "            i += 1\n",
    "            if dataList[i] != 'None':\n",
    "                node.right = TreeNode(int(dataList[i]))\n",
    "                queue.append(node.right)\n",
    "            i += 1\n",
    "        return root\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        def traverse(root):\n",
    "            if not root:\n",
    "                res.append(\"null\")\n",
    "                return\n",
    "            res.append(str(root.val))\n",
    "            traverse(root.left)\n",
    "            traverse(root.right)\n",
    "        traverse(root)\n",
    "        return \"#\".join(res)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        res = data.split(\"#\")[::-1]\n",
    "\n",
    "        def construct(res):\n",
    "            if not res:\n",
    "                return\n",
    "            root_val = res.pop()\n",
    "            if root_val == \"null\":\n",
    "                return\n",
    "            root = TreeNode(int(root_val))\n",
    "            root.left = construct(res)\n",
    "            root.right = construct(res)\n",
    "            return root\n",
    "        return construct(res)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root: return \"*\"\n",
    "        return self.serialize(root.left) + \",\" + self.serialize(root.right) + \",\" + str(root.val)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return self.buildTree(data.split(\",\"))\n",
    "\n",
    "    def buildTree(self, nodes: List[str]) -> Optional[TreeNode]:\n",
    "        if not nodes: return None\n",
    "        nodeVal = nodes.pop()\n",
    "        if nodeVal == \"*\": return None\n",
    "        node = TreeNode(int(nodeVal))\n",
    "        node.right = self.buildTree(nodes)\n",
    "        node.left = self.buildTree(nodes)\n",
    "        return node\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return str(root.val) + \" \" + self.serialize(root.left) + \" \" + self.serialize(root.right) if root else \"null\"\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        valList = data.split()\n",
    "        p = 0\n",
    "        def dfs():\n",
    "            nonlocal p, valList\n",
    "            if valList[p] == 'null':\n",
    "                p += 1\n",
    "                return None\n",
    "            else:\n",
    "                r = TreeNode(int(valList[p]))\n",
    "                p += 1\n",
    "                r.left = dfs()\n",
    "                r.right = dfs()\n",
    "                return r\n",
    "\n",
    "        return dfs()\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# https://mp.weixin.qq.com/s/DVX2A1ha4xSecEXLxW_UsA\n",
    "# 哦，原来前序遍历的意思是：先遍历根节点，再遍历左子树，最后遍历右子树\n",
    "# 本题考查：已知一个前序遍历结果列表，里面包含了空指针，如何构造一颗二叉树。\n",
    "# 而前面的题是已已知2个序遍历结果，没有空指针信息，如何构建一颗二叉树\n",
    "\n",
    "# 方法一：前序遍历实现的序列化、反序列化方法。掌握这一种方法就行了。其他两种知道下就行了\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        # 用于拼接字符串\n",
    "        self.res = []\n",
    "    \n",
    "    # 先序列化成列表，并带上空指针\n",
    "    # 题目后面有注释说了，ser这个序列化函数的返回结果会自动传递给deser这个函数的\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.traverse(root)\n",
    "\n",
    "        return \"\".join(self.res)\n",
    "    \n",
    "    # 将二叉树打平为字符串\n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            # 定义一个常量，表示空节点，也可以定义成常量放进init里\n",
    "            self.res.append(\"#\")\n",
    "            # 定义一个常量，表示分隔符，也可以定义成常量放进init里\n",
    "            self.res.append(\",\")\n",
    "            return\n",
    "        \n",
    "        self.res.append(str(root.val)) # 这里str的原因是：后面会把list转为str，所以list里的元素都必须为str，而不是部分str部分int会报错的\n",
    "        self.res.append(\",\")\n",
    "\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)\n",
    "\n",
    "    # 主函数，将字符串反序列化为二叉树结构\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        # data = \"\".join(self.res)\n",
    "        nodes = data.split(\",\")\n",
    "\n",
    "        return self._deserialize(nodes)\n",
    "    \n",
    "    def _deserialize(self, data):\n",
    "        # 如果列表为空，返回空节点\n",
    "        if not data:\n",
    "            return None\n",
    "\n",
    "        # 前序遍历位置\n",
    "        # 列表最左侧就是根节点\n",
    "        root_val = data.pop(0)\n",
    "        if root_val == \"#\": # 遇见空指针,如果是空节点，返回空节点\n",
    "            return None\n",
    "        root = TreeNode(int(root_val))\n",
    "\n",
    "        # 递归地构造左右子树\n",
    "        root.left = self._deserialize(data)\n",
    "        root.right = self._deserialize(data)\n",
    "\n",
    "        # 返回根节点\n",
    "        return root\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))\n",
    "\n",
    "# 方法二：后序遍历实现的序列化、反序列化方法\n",
    "# class Codec:\n",
    "#     def __init__(self):\n",
    "#         # 用于拼接字符串\n",
    "#         self.res = []\n",
    "    \n",
    "#     # 先序列化成列表，并带上空指针\n",
    "#     # 题目后面有注释说了，ser这个序列化函数的返回结果会自动传递给deser这个函数的\n",
    "#     def serialize(self, root):\n",
    "#         \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "#         :type root: TreeNode\n",
    "#         :rtype: str\n",
    "#         \"\"\"\n",
    "#         self.traverse(root)\n",
    "\n",
    "#         return \"\".join(self.res)\n",
    "    \n",
    "#     # 将二叉树打平为字符串\n",
    "#     def traverse(self, root):\n",
    "#         if not root:\n",
    "#             # 定义一个常量，表示空节点，也可以定义成常量放进init里\n",
    "#             self.res.append(\"#\")\n",
    "#             # 定义一个常量，表示分隔符，也可以定义成常量放进init里\n",
    "#             self.res.append(\",\")\n",
    "#             return\n",
    "\n",
    "#         self.traverse(root.left)\n",
    "#         self.traverse(root.right)\n",
    "#         self.res.append(str(root.val)) # 这里str的原因是：后面会把list转为str，所以list里的元素都必须为str，而不是部分str部分int会报错的\n",
    "#         self.res.append(\",\")\n",
    "\n",
    "#     # 主函数，将字符串反序列化为二叉树结构\n",
    "#     def deserialize(self, data):\n",
    "#         \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "#         :type data: str\n",
    "#         :rtype: TreeNode\n",
    "#         \"\"\"\n",
    "#         nodes = data.split(\",\")\n",
    "\n",
    "#         return self._deserialize(nodes)\n",
    "    \n",
    "#     def _deserialize(self, data):\n",
    "#         # 如果列表为空，返回空节点\n",
    "#         if not data:\n",
    "#             return None\n",
    "\n",
    "#         # 后序遍历位置\n",
    "#         # 列表最右侧就是根节点\n",
    "#         # 这里pop的总是列表最后一个元素。而后序遍历是左子树、右子树、根节点的顺序。\n",
    "#         # 因为pop总的总是最后一个元素，所以pop完根节点之后，就该pop右子树的节点了。所以递归的时候，要先递归右子树，在递归左子树\n",
    "#         root_val = data.pop()\n",
    "#         if root_val == \"#\": # 遇见空指针,如果是空节点，返回空节点\n",
    "#             return None\n",
    "#         root = TreeNode(int(root_val))\n",
    "\n",
    "#         # 递归地构造左右子树\n",
    "#         root.right = self._deserialize(data)\n",
    "#         root.left = self._deserialize(data)\n",
    "        \n",
    "#         # 返回根节点\n",
    "#         return root\n",
    "\n",
    "# # 方法三：层序遍历。我就不写了。也挺好理解的，不用掌握\n",
    "\n",
    "# # 定义一个常量，表示分隔符\n",
    "# SEP = \",\"\n",
    "# # 定义一个常量，表示空节点\n",
    "# NULL = \"#\"\n",
    "\n",
    "# # 定义一个函数，将二叉树序列化为字符串\n",
    "# def serialize(root):\n",
    "#     if root is None: # 如果根节点为空，返回空字符串\n",
    "#         return \"\"\n",
    "#     sb = [] # 定义一个列表，用来存储字符串\n",
    "#     # 初始化队列，将 root 加入队列\n",
    "#     q = [root]\n",
    "    \n",
    "#     while q: # 当队列不为空时，循环执行以下操作\n",
    "#         cur = q.pop(0) # 弹出队列的第一个元素\n",
    "        \n",
    "#         # 层级遍历代码位置\n",
    "#         if cur is None: # 如果当前节点为空\n",
    "#             sb.append(NULL + SEP) # 将空节点的标识符和分隔符加入列表\n",
    "#             continue # 跳过后续操作\n",
    "#         sb.append(str(cur.val) + SEP) # 将当前节点的值和分隔符加入列表\n",
    "#         # 将当前节点的左右子节点加入队列\n",
    "#         q.append(cur.left)\n",
    "#         q.append(cur.right)\n",
    "    \n",
    "#     return \"\".join(sb) # 将列表中的字符串拼接起来，返回结果\n",
    "\n",
    "\n",
    "# # 将字符串反序列化为二叉树结构\n",
    "# def deserialize(data):\n",
    "#     if not data: return None\n",
    "#     nodes = data.split(SEP)\n",
    "#     # 第一个元素就是 root 的值\n",
    "#     root = TreeNode(int(nodes[0]))\n",
    "\n",
    "#     # 队列 q 记录父节点，将 root 加入队列\n",
    "#     q = collections.deque()\n",
    "#     q.append(root)\n",
    "\n",
    "#     i = 1\n",
    "#     while q:\n",
    "#         # 队列中存的都是父节点\n",
    "#         parent = q.popleft()\n",
    "#         # 父节点对应的左侧子节点的值\n",
    "#         left = nodes[i]\n",
    "#         i += 1\n",
    "#         if left != NULL:\n",
    "#             parent.left = TreeNode(int(left))\n",
    "#             q.append(parent.left)\n",
    "#         else:\n",
    "#             parent.left = None\n",
    "#         # 父节点对应的右侧子节点的值\n",
    "#         right = nodes[i]\n",
    "#         i += 1\n",
    "#         if right != NULL:\n",
    "#             parent.right = TreeNode(int(right))\n",
    "#             q.append(parent.right)\n",
    "#         else:\n",
    "#             parent.right = None\n",
    "#     return root\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.alist = []\n",
    "        def preorder(root):\n",
    "            if not root:\n",
    "                self.alist.append('#')\n",
    "                return \n",
    "            self.alist.append(str(root.val))\n",
    "            preorder(root.left)\n",
    "            preorder(root.right)\n",
    "        preorder(root)\n",
    "        return ','.join(self.alist)\n",
    "\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        arr = data.split(',')\n",
    "        alen = len(arr)\n",
    "        if alen == 2:return None\n",
    "        return self.buildTree(arr)\n",
    "    \n",
    "    def buildTree(self,arr):\n",
    "        if arr[0] == '#':\n",
    "            del arr[0]\n",
    "            return None\n",
    "        root = TreeNode(int(arr[0]))\n",
    "        del arr[0]\n",
    "        root.left = self.buildTree(arr)\n",
    "        root.right = self.buildTree(arr)\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        ret=[]\n",
    "        dq=deque([root])\n",
    "        while dq:\n",
    "            node=dq.popleft()\n",
    "            if node:\n",
    "                ret.append(str(node.val))\n",
    "                dq.append(node.left)\n",
    "                dq.append(node.right)\n",
    "            else:\n",
    "                ret.append('None')\n",
    "        return ','.join(ret)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return\n",
    "        dataList=data.split(',')\n",
    "        root=TreeNode(int(dataList[0]))\n",
    "        dq=deque([root])\n",
    "        i=1\n",
    "        while dq:\n",
    "            node=dq.popleft()\n",
    "            if dataList[i] != 'None':\n",
    "                node.left=TreeNode(int(dataList[i]))\n",
    "                dq.append(node.left)\n",
    "            i+=1\n",
    "            if dataList[i] !='None':\n",
    "                node.right=TreeNode(int(dataList[i]))\n",
    "                dq.append(node.right)\n",
    "            i+=1\n",
    "        return root\n",
    "               \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res = []\n",
    "\n",
    "        def preorder(root):\n",
    "            if not root:\n",
    "                res.append('n')\n",
    "                return\n",
    "            res.append(str(root.val))\n",
    "            preorder(root.left)\n",
    "            preorder(root.right)\n",
    "\n",
    "        preorder(root)\n",
    "        return ','.join(res)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        arr = data.split(',')\n",
    "        arr.reverse()\n",
    "        def preorder():\n",
    "            if not arr:\n",
    "                return\n",
    "            if arr[-1] =='n':\n",
    "                arr.pop()\n",
    "                return\n",
    "            root = TreeNode(int(arr.pop()))\n",
    "            root.left = preorder()\n",
    "            root.right =preorder()\n",
    "            return  root\n",
    "        return preorder()\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root: Optional[TreeNode]) -> str:\n",
    "        ans = []\n",
    "        def f(node: Optional[TreeNode]) -> None:\n",
    "            if not node:\n",
    "                ans.append('x')\n",
    "                return \n",
    "            ans.append(str(node.val))\n",
    "            f(node.left)\n",
    "            f(node.right)\n",
    "        f(root)\n",
    "        return ','.join(ans)\n",
    "\n",
    "    def deserialize(self, data: str) -> Optional[TreeNode]:\n",
    "        vals = data.split(',')\n",
    "        cnt = 0\n",
    "        def g() -> Optional[TreeNode]:\n",
    "            nonlocal cnt\n",
    "            if vals[cnt] == 'x':\n",
    "                cnt += 1\n",
    "                return None\n",
    "            node = TreeNode(int(vals[cnt]))\n",
    "            cnt += 1\n",
    "            node.left = g()\n",
    "            node.right = g()\n",
    "            return node\n",
    "        return g()\n",
    "            \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root: TreeNode):\n",
    "        \"\"\"\n",
    "        Encodes a tree to a single string.\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return ''\n",
    "        return \",\".join(self.level_serialize(root))\n",
    "\n",
    "    def level_serialize(self, root: Optional[TreeNode]):\n",
    "        \"\"\"\n",
    "        前序遍历序列化\n",
    "        \"\"\"\n",
    "        arr = []\n",
    "        first_nodes = [root]\n",
    "        while len(first_nodes) > 0:\n",
    "            second_nodes = []\n",
    "            for node in first_nodes:\n",
    "                if node is None:\n",
    "                    arr.append('#')\n",
    "                    continue\n",
    "                arr.append(str(node.val))\n",
    "                second_nodes.append(node.left)\n",
    "                second_nodes.append(node.right)\n",
    "            first_nodes = second_nodes\n",
    "\n",
    "        return arr\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"\n",
    "        Decodes your encoded data to tree.\n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if len(data) == 0:\n",
    "            return None\n",
    "        arr = data.split(',')\n",
    "        return self.level_deserialize(arr)\n",
    "\n",
    "    def level_deserialize(self, arr):\n",
    "        root = TreeNode(arr[0])\n",
    "        nodes = [root]\n",
    "        arr.pop(0)\n",
    "        while len(nodes) > 0:\n",
    "            cur_node = nodes.pop(0)\n",
    "            if len(arr) == 0:\n",
    "                break\n",
    "            first_val = arr.pop(0)\n",
    "            if first_val != '#':\n",
    "                node = TreeNode(int(first_val))\n",
    "                cur_node.left = node\n",
    "                nodes.append(node)\n",
    "\n",
    "            first_val = arr.pop(0)\n",
    "            if first_val != '#':\n",
    "                node = TreeNode(int(first_val))\n",
    "                cur_node.right = node\n",
    "                nodes.append(node)\n",
    "        return root\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return ''\n",
    "        data_ls = []\n",
    "        string = ''\n",
    "        old_queue = []\n",
    "        new_queue = [root]\n",
    "        while new_queue:\n",
    "            old_queue = new_queue\n",
    "            new_queue = []\n",
    "            while old_queue:\n",
    "                node = old_queue.pop(0)\n",
    "                if node:\n",
    "                    data_ls.append(node.val)\n",
    "                    new_queue.append(node.left)\n",
    "                    new_queue.append(node.right)\n",
    "                else:\n",
    "                    data_ls.append(sys.maxsize)\n",
    "            string += ';'.join(list(map(str, data_ls)))\n",
    "            string += '\\n'\n",
    "            data_ls = []\n",
    "        return string\n",
    "\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == '':\n",
    "            return None\n",
    "        data_ls = data.split()\n",
    "        root = TreeNode(int(data_ls[0]))\n",
    "        queue = [root]\n",
    "        for data_str in data_ls[1:]:\n",
    "            for index, val in enumerate(data_str.split(';')):\n",
    "                if index % 2 == 0:  \n",
    "                    node = queue.pop(0)\n",
    "                    node.left = TreeNode(int(val)) if val != str(sys.maxsize) else None\n",
    "                    if node.left:\n",
    "                        queue.append(node.left)\n",
    "                else:\n",
    "                    node.right = TreeNode(int(val)) if val != str(sys.maxsize) else None\n",
    "                    if node.right:\n",
    "                        queue.append(node.right)\n",
    "        return root\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return '[]'\n",
    "        queue = [root]\n",
    "        ans = []\n",
    "        a = []\n",
    "\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            if cur: \n",
    "                ans.append(cur.val)\n",
    "                queue.append(cur.left)\n",
    "                queue.append(cur.right)\n",
    "            else:\n",
    "                ans.append(1001)\n",
    "\n",
    "        print(ans)\n",
    "        return str(ans)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        data = data.strip('[]')\n",
    "        datas = data.split(',')\n",
    "        if datas == [''] or int(datas[0]) == 1001:\n",
    "            return []\n",
    "        root = TreeNode(int(datas[0]))\n",
    "        queue = [root]\n",
    "\n",
    "\n",
    "        for i in range(len(datas) // 2):\n",
    "            left = int(datas[i * 2 + 1])\n",
    "            right = int(datas[ i * 2 + 2])\n",
    "            cur = queue.pop(0)\n",
    "            if left != 1001:\n",
    "                cur.left = TreeNode(int(left))\n",
    "                queue.append(cur.left)\n",
    "            if right != 1001:\n",
    "                cur.right = TreeNode(int(right))\n",
    "                queue.append(cur.right)\n",
    "        return root\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def _s2i(self, s):\n",
    "        f = 1\n",
    "        if s[0] == '-':\n",
    "            f, s = -1, s[1:]\n",
    "        k = 0\n",
    "        while (len(s) > 0) and (s[0] not in ('[','n',']')):\n",
    "            k = k * 10 + int(s[0])\n",
    "            s = s[1:]\n",
    "        return (k*f, s)\n",
    "    \n",
    "    def serialize(self, root: TreeNode) -> str:\n",
    "        if root is None:\n",
    "            return 'n'\n",
    "        s = \"\"\n",
    "        if root.right:\n",
    "            s = self.serialize(root.right)\n",
    "        if root.left or s != \"\":\n",
    "            s = self.serialize(root.left) + s\n",
    "        return \"[%d%s]\" % (root.val, s)\n",
    "\n",
    "    def _des(self, data:str) -> (TreeNode, str):\n",
    "        if data[0] == 'n':\n",
    "            return None, data[1:]\n",
    "        if data[0] == ']':\n",
    "            return None, data\n",
    "        assert(data[0]=='[')\n",
    "        data = data[1:]\n",
    "        v, data = self._s2i(data)\n",
    "        left, data = self._des(data)\n",
    "        right, data = self._des(data)\n",
    "        assert(data[0] == ']')\n",
    "        return TreeNode(v,left,right), data[1:]\n",
    "        \n",
    "    def deserialize(self, data: str) -> TreeNode:\n",
    "        root, _ = self._des(data)\n",
    "        return root\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.flag = 0\n",
    "\n",
    "    def f(self, root, data):\n",
    "        if root is None:\n",
    "            data += '#,'\n",
    "            return data\n",
    "        data += str(root.val)+','\n",
    "        data = self.f(root.left, data)\n",
    "        data = self.f(root.right, data)\n",
    "        return data\n",
    "\n",
    "    \n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return self.f(root, '')\n",
    "        \n",
    "    def g(self, val):\n",
    "        if val[self.flag]=='#':\n",
    "            self.flag += 1\n",
    "            return None\n",
    "        p = TreeNode(val[self.flag])\n",
    "        self.flag += 1\n",
    "        p.left = self.g(val)\n",
    "        p.right = self.g(val)\n",
    "        return p\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return self.g(data.split(','))\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root, str1 = \"\"):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            str1 += \"None,\" \n",
    "        else:\n",
    "            str1 = str(str1) + str(root.val) + \",\"\n",
    "            str1 = self.serialize(root.left, str1)\n",
    "            str1 = self.serialize(root.right, str1)\n",
    "        return str1\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        print(data)\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        root, data = self.deserialize_data(data)\n",
    "        return root\n",
    "    \n",
    "    def deserialize_data(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        val = data.split(\",\")[0]\n",
    "        if val == \"None\":\n",
    "            data = data.lstrip(val)\n",
    "            data = data.lstrip(\",\")\n",
    "            return None, data\n",
    "        root = TreeNode(val)\n",
    "        data = data.lstrip(val)\n",
    "        data = data.lstrip(\",\")\n",
    "        root.left, data = self.deserialize_data(data)\n",
    "        root.right, data = self.deserialize_data(data)\n",
    "        return root, data\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return self.rserialize(root, \"\")\n",
    "\n",
    "    def rserialize(self, node, s):\n",
    "\n",
    "        if not node: return s + \"None,\"\n",
    "        s += f\"{node.val},\"\n",
    "        s = self.rserialize(node.left, s)\n",
    "        s = self.rserialize(node.right, s)\n",
    "        return s\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data[0] == \"None\": return None\n",
    "        self.data = data.split(\",\")[:-1]\n",
    "        return self.rdeserialize(self.data)\n",
    "\n",
    "    def rdeserialize(self, data):\n",
    "        if self.data[0] == \"None\":\n",
    "            self.data.pop(0)\n",
    "            return None\n",
    "        node = TreeNode(int(self.data.pop(0)))\n",
    "        node.left = self.rdeserialize(self.data)\n",
    "        node.right = self.rdeserialize(self.data)\n",
    "\n",
    "        return node        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def dfs(node,s):\n",
    "            if not node: \n",
    "                s+='None,'\n",
    "                return s\n",
    "            s=s+str(node.val)+','\n",
    "            s=dfs(node.left,s)\n",
    "            s=dfs(node.right,s)\n",
    "            return s\n",
    "       \n",
    "        return dfs(root,'')\n",
    "\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        nums=data.split(',')\n",
    "        nums.pop(-1)\n",
    "        def dfs(nums):\n",
    "            tmp=nums.pop(0)\n",
    "            if tmp=='None':\n",
    "                return None\n",
    "            node=TreeNode(int(tmp))\n",
    "            node.left=dfs(nums)\n",
    "            node.right=dfs(nums)\n",
    "            return node\n",
    "        return dfs(nums)\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return self.rserialize(root, \"\")\n",
    "\n",
    "    def rserialize(self, node, s):\n",
    "\n",
    "        if not node: return s + \"None,\"\n",
    "        s += f\"{node.val},\"\n",
    "        s = self.rserialize(node.left, s)\n",
    "        s = self.rserialize(node.right, s)\n",
    "        return s\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data[0] == \"None\": return None\n",
    "        self.data = data.split(\",\")[:-1]\n",
    "        return self.rdeserialize(self.data)\n",
    "\n",
    "    def rdeserialize(self, data):\n",
    "        if self.data[0] == \"None\":\n",
    "            self.data.pop(0)\n",
    "            return None\n",
    "        node = TreeNode(int(self.data.pop(0)))\n",
    "        node.left = self.rdeserialize(self.data)\n",
    "        node.right = self.rdeserialize(self.data)\n",
    "\n",
    "        return node        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def dfs(node,s):\n",
    "            if not node: \n",
    "                s+='None,'\n",
    "                return s\n",
    "            s=s+str(node.val)+','\n",
    "            s=dfs(node.left,s)\n",
    "            s=dfs(node.right,s)\n",
    "            return s\n",
    "        res=dfs(root,'')\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        \n",
    "        nums=data.split(',')\n",
    "        nums.pop(-1)\n",
    "        if nums[0]=='None': return None\n",
    "\n",
    "        def dfs(nums):\n",
    "            if not nums: \n",
    "                return \n",
    "            if nums[0]==\"None\": \n",
    "                nums.pop(0)\n",
    "                return None\n",
    "            cur=TreeNode(int(nums[0]))\n",
    "            nums.pop(0)\n",
    "            \n",
    "            cur.left=dfs(nums)\n",
    "            \n",
    "\n",
    "            cur.right=dfs(nums)\n",
    "            return cur\n",
    "        return dfs(nums)\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"\"\n",
    "        \n",
    "        l = [[(1, root)]]\n",
    "        while 1:\n",
    "            now = []\n",
    "            for n, node in l[-1]:\n",
    "                if node.left:\n",
    "                    now.append((n * 2, node.left))\n",
    "                if node.right:\n",
    "                    now.append((n * 2 + 1, node.right))\n",
    "            if now:\n",
    "                l.append(now)\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        ret = \"\"\n",
    "        for row in l:\n",
    "            now = []\n",
    "            for n, node in row:\n",
    "                now.append((n, node.val))\n",
    "            ret += \"\\0\" + str(now)\n",
    "        return ret[1:]\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return\n",
    "\n",
    "        l = [eval(e) for e in data.split(\"\\0\")]\n",
    "        root = TreeNode(l[0][0][1])\n",
    "        d = {1: root}\n",
    "\n",
    "        for i in range(1, len(l)):\n",
    "            for n, val in l[i]:\n",
    "                node = TreeNode(val)\n",
    "                d[n] = node\n",
    "\n",
    "                if n % 2:\n",
    "                    d[n // 2].right = node\n",
    "                else:\n",
    "                    d[n // 2].left = node\n",
    "\n",
    "        return root\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        listSeries = self.__serializeAsList(root)\n",
    "        stringSeries = ','.join([self.__objToString(el) for el in listSeries])\n",
    "        return(stringSeries)\n",
    "    \n",
    "    def deserialize(self, data):\n",
    "        head, _ = self.__deserializeHelper(data.split(','), 0)\n",
    "        return(head)\n",
    "\n",
    "    def __objToString(self,el):\n",
    "        if el == None: return('None')\n",
    "        else: return(str(el))\n",
    "        \n",
    "    def __serializeAsList(self, root):\n",
    "        if root == None:\n",
    "            serial = [None]\n",
    "        else:\n",
    "            serial = [root.val]\n",
    "            serial += self.__serializeAsList(root.left)\n",
    "            serial += self.__serializeAsList(root.right)\n",
    "        return(serial)\n",
    "    \n",
    "    def __deserializeHelper(self,data,i):\n",
    "        nextObj = self.__stringToObj(data[i])\n",
    "        i += 1\n",
    "        if nextObj == None:\n",
    "            return(None,i)\n",
    "        head = TreeNode(nextObj)\n",
    "        head.left,  i = self.__deserializeHelper(data,i)\n",
    "        head.right, i = self.__deserializeHelper(data,i)\n",
    "        return(head,i)\n",
    "     \n",
    "    def __stringToObj(self,string):\n",
    "        if string == 'None': return(None)\n",
    "        else: return(int(string))\n",
    "\n",
    "\n",
    "# Possible orderings: \n",
    "#               time(ser)   space(ser)      time(deser.)    space(deser)\n",
    "# In-order      O(n)        O(depth)        O(n)            O(depth)\n",
    "# Pre-order     O(n)        \n",
    "# Post-order\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return root\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return data\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "#     def serialize(self, root):\n",
    "#         \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "#         :type root: TreeNode\n",
    "#         :rtype: str\n",
    "#         \"\"\"\n",
    "#         if not root:\n",
    "#             return '[]'\n",
    "#         out=[root.val]\n",
    "#         temp=[root]\n",
    "#         while temp:\n",
    "#             Next=[]\n",
    "#             for i in temp:\n",
    "#                 if i:\n",
    "#                     Next.extend([i.left,i.right])\n",
    "#             if Next:\n",
    "#                 for i in temp:\n",
    "#                     if i:\n",
    "#                         out.append(i.val)\n",
    "#                     else:\n",
    "#                         out.append(None)\n",
    "#             temp=Next\n",
    "#         out.pop(0)\n",
    "#         return str(out)\n",
    "        \n",
    "\n",
    "#     def deserialize(self, data):\n",
    "#         \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "#         :type data: str\n",
    "#         :rtype: TreeNode\n",
    "#         \"\"\"\n",
    "        \n",
    "#         if data=='[]':\n",
    "#             return None\n",
    "#         list1=data[1:-1].split(', ')\n",
    "#         root=TreeNode(int(list1[0]))\n",
    "#         temp=[root]\n",
    "#         list1.pop(0)\n",
    "#         while len(list1):\n",
    "#             Next=[]\n",
    "#             for i in temp:\n",
    "#                 if list1[0]!='None':\n",
    "#                     i.left=TreeNode(int(list1[0]))\n",
    "#                     Next.append(i.left)\n",
    "#                 list1.pop(0)\n",
    "#                 if list1[0]!='None':\n",
    "#                     i.right=TreeNode(int(list1[0]))\n",
    "#                     Next.append(i.right)\n",
    "#                 list1.pop(0) \n",
    "#             temp=Next\n",
    "#         return root\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return []\n",
    "        seria=[root.val]\n",
    "        l=[]\n",
    "        l.append(root)\n",
    "        while True:\n",
    "            lens=len(l)\n",
    "            for i in range(0,lens):\n",
    "                if l[i]!=None:\n",
    "                    l.append(l[i].left)\n",
    "                    l.append(l[i].right)\n",
    "            del l[0:lens]\n",
    "            #exist\n",
    "            if set(l)=={None}:\n",
    "                break\n",
    "            for i in l:\n",
    "                if i!=None:\n",
    "                    seria.append(i.val)\n",
    "                else:\n",
    "                    seria.append(None)\n",
    "        for i in reversed(seria):\n",
    "            if i==None:\n",
    "                del seria[-1]\n",
    "            else:\n",
    "                break\n",
    "        print(seria)\n",
    "        return seria\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return data\n",
    "            \n",
    "            \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        ans = ''\n",
    "\n",
    "        if not root:\n",
    "            return ans\n",
    "\n",
    "        queue = collections.deque([root])\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "\n",
    "            if node:\n",
    "                ans += f'{node.val},'\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else:\n",
    "                ans += '.,'\n",
    "\n",
    "        i = len(ans)\n",
    "\n",
    "        while i >= 0 and ans[i - 2:i] == '.,':\n",
    "            i -= 2\n",
    "\n",
    "        return ans[:i - 1]  # to evict the last ','\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "\n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return\n",
    "\n",
    "        vals = iter(data.split(','))\n",
    "        root = TreeNode(next(vals))\n",
    "        queue = collections.deque([root])\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "\n",
    "            for child in ('left', 'right'):\n",
    "                val = next(vals, '.')\n",
    "\n",
    "                if val != '.':\n",
    "                    setattr(node, child, TreeNode(int(val)))\n",
    "                    queue.append(getattr(node, child))\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        queue = []\n",
    "        ret = ''\n",
    "        if root:\n",
    "            queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if node:\n",
    "                ret = ret + str(node.val) + ' '\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else:\n",
    "                ret = ret + 'n '\n",
    "        \n",
    "        ret = ret.strip()\n",
    "\n",
    "        return ret\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def convert(x):\n",
    "            if x == 'n':\n",
    "                return None\n",
    "            else:\n",
    "                return int(x)\n",
    "            \n",
    "        if data == '':\n",
    "            return None\n",
    "        data = list(map(convert, data.split(' ')))\n",
    "        queue, i = [], 0\n",
    "        root = TreeNode(data[0])\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            i += 1\n",
    "            if data[i] is not None:\n",
    "                left = TreeNode(data[i])\n",
    "                queue.append(left)\n",
    "                node.left = left\n",
    "            i += 1\n",
    "            if data[i] is not None:\n",
    "                right = TreeNode(data[i])\n",
    "                queue.append(right)\n",
    "                node.right = right\n",
    "        \n",
    "        return root\n",
    "        \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import collections\n",
    "class Codec:\n",
    "    #  Solution 1:深度遍历(前序遍历)序列化和反序列化的方式\n",
    "#     def serialize(self, root):\n",
    "#         \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "#         :type root: TreeNode\n",
    "#         :rtype: str\n",
    "#         \"\"\"\n",
    "#         ser = []\n",
    "#         def preOrder(root):\n",
    "#             if not root:\n",
    "#                 ser.append('#')\n",
    "#             else:\n",
    "#                 ser.append(str(root.val))\n",
    "#                 preOrder(root.left)\n",
    "#                 preOrder(root.right)\n",
    "#         preOrder(root)\n",
    "#         return ' '.join(ser)\n",
    "        \n",
    "        \n",
    "\n",
    "#     def deserialize(self, data):\n",
    "#         \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "#         :type data: str\n",
    "#         :rtype: TreeNode\n",
    "#         \"\"\"\n",
    "#         vals = collections.deque([x for x in data.split()])\n",
    "#         def build():\n",
    "#             if vals:\n",
    "#                 val = vals.popleft()\n",
    "#                 if val == '#':\n",
    "#                     return None\n",
    "#                 else:\n",
    "#                     root = TreeNode(int(val))\n",
    "#                     root.left = build()\n",
    "#                     root.right = build()\n",
    "#                 return root\n",
    "#         return build()\n",
    "    # Solution 2: 层次遍历序列化和反序列化的方式\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        \n",
    "        ser = []\n",
    "        serroot = [root]\n",
    "        while serroot:\n",
    "            rootone = serroot.pop(0)\n",
    "            if rootone:\n",
    "                ser.append(str(rootone.val))\n",
    "                serroot.append(rootone.left)\n",
    "                serroot.append(rootone.right)\n",
    "            else:\n",
    "                ser.append('#')\n",
    "        return ' '.join(ser)\n",
    "    \n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        curdata = collections.deque()\n",
    "        cur = None\n",
    "        vals = collections.deque([x for x in data.split()])\n",
    "        if vals:\n",
    "            val = vals.popleft()\n",
    "            if val != '#':\n",
    "                cur = TreeNode(val)\n",
    "                curdata.append(cur)\n",
    "        while vals and curdata:\n",
    "            val = vals.popleft()\n",
    "            curone = curdata.popleft()\n",
    "            if not val:\n",
    "                break\n",
    "            if val != '#':\n",
    "                curleft = TreeNode(val)\n",
    "                curone.left = curleft\n",
    "                curdata.append(curleft)\n",
    "            val = vals.popleft()\n",
    "            if not val:\n",
    "                break\n",
    "            if val != '#':\n",
    "                curright = TreeNode(val)\n",
    "                curone.right = curright\n",
    "                curdata.append(curright)\n",
    "        return cur\n",
    "            \n",
    "                \n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import collections\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        ser = []\n",
    "        def preOrder(root):\n",
    "            if not root:\n",
    "                ser.append('#')\n",
    "            else:\n",
    "                ser.append(str(root.val))\n",
    "                preOrder(root.left)\n",
    "                preOrder(root.right)\n",
    "        preOrder(root)\n",
    "        # print(ser)\n",
    "        return ' '.join(ser)\n",
    "        \n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        vals = collections.deque([x for x in data.split()])\n",
    "        def build():\n",
    "            if vals:\n",
    "                val = vals.popleft()\n",
    "                if val == '#':\n",
    "                    return None\n",
    "                else:\n",
    "                    root = TreeNode(int(val))\n",
    "                    root.left = build()\n",
    "                    root.right = build()\n",
    "                return root\n",
    "        return build()\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    \n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        vals = []\n",
    "        def doit(root):\n",
    "            if root :\n",
    "                vals.append(str(root.val))\n",
    "                doit(root.left)\n",
    "                doit(root.right)\n",
    "            else:\n",
    "                vals.append(\"#\")    \n",
    "        doit(root)\n",
    "        return \" \".join(vals)\n",
    "    \n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        vals = iter(data.split())\n",
    "        def doit():\n",
    "            val = next(vals)\n",
    "            if val==\"#\":\n",
    "                return None\n",
    "            # elif val==\"-\":\n",
    "            #     val = \"-\" + next(vals)\n",
    "            none = TreeNode(int(val))\n",
    "            none.left = doit()\n",
    "            none.right = doit()\n",
    "            return none\n",
    "        return doit()\n",
    "    \n",
    "            \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()   \n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        \n",
    "        if not root: return ''\n",
    "        \n",
    "        res = [str(root.val)]\n",
    "        nodes = [root]\n",
    "        i = 0\n",
    "        \n",
    "        while i < len(nodes):\n",
    "            if nodes[i].left:\n",
    "                nodes.append(nodes[i].left)\n",
    "                res.append(str(nodes[i].left.val))\n",
    "            else:\n",
    "                res.append('#')\n",
    "            if nodes[i].right:\n",
    "                nodes.append(nodes[i].right)\n",
    "                res.append(str(nodes[i].right.val))\n",
    "            else:\n",
    "                res.append('#')\n",
    "            i += 1\n",
    "        \n",
    "        while res[-1] == '#': res.pop()\n",
    "        return ','.join(res)\n",
    "        \n",
    "        \n",
    "    \n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        \n",
    "        if not data: return None\n",
    "        \n",
    "        data = data.split(',')\n",
    "        nodes = [TreeNode(int(data[0]))]\n",
    "        \n",
    "        i, j = 1, 0\n",
    "        left = True\n",
    "        \n",
    "        while i < len(data):\n",
    "            if data[i] != '#':\n",
    "                new = TreeNode(int(data[i]))\n",
    "                nodes.append(new)\n",
    "            else:\n",
    "                new = None\n",
    "            \n",
    "            if left: nodes[j].left = new\n",
    "            else: nodes[j].right = new; j += 1\n",
    "            \n",
    "            left = not left\n",
    "            i += 1\n",
    "        \n",
    "        return nodes[0]\n",
    "                \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        l_node = [root]\n",
    "        seq = []\n",
    "        ni = 0\n",
    "        while ni < len(l_node):\n",
    "            cur = l_node[ni]\n",
    "            if cur:  \n",
    "                seq.append(str(cur.val))\n",
    "                l_node.extend([cur.left, cur.right])\n",
    "            else:\n",
    "                seq.append('null')\n",
    "            ni += 1\n",
    "        return '['+','.join(seq)+']'\n",
    "            \n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"        \n",
    "        data = data[1:-1].split(',')\n",
    "        root_val = data[0]\n",
    "        if root_val == 'null':\n",
    "            return []\n",
    "        else:\n",
    "            root = TreeNode(root_val)\n",
    "        node = [root]\n",
    "        di = 1\n",
    "        ni = 0\n",
    "        while di < len(data):\n",
    "            cur = node[ni]\n",
    "            if cur:\n",
    "                val_l = data[di]\n",
    "                val_r = data[di+1]\n",
    "                cur.left = TreeNode(int(val_l)) if val_l != 'null' else None\n",
    "                cur.right = TreeNode(int(val_r)) if val_r != 'null' else None\n",
    "                node.extend([cur.left, cur.right])\n",
    "                di += 2\n",
    "            ni += 1\n",
    "        return root\n",
    "            \n",
    "            \n",
    "        \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def inorder(node, dicti = {}):\n",
    "            if not node:\n",
    "                return []\n",
    "            if node.val in dicti:\n",
    "                dicti[node.val] += 1\n",
    "            else:\n",
    "                dicti[node.val] = 1\n",
    "            node.val = str(node.val) + \"_\" + str(dicti[node.val])\n",
    "            return inorder(node.left) + [node.val] + inorder(node.right)\n",
    "        \n",
    "        def postorder(node):\n",
    "            if not node:\n",
    "                return []\n",
    "            return postorder(node.left) + postorder(node.right) + [node.val]\n",
    "        \n",
    "        return \"^\".join([\" \".join(inorder(root)), \" \".join(postorder(root))])\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def helper(stop = None):\n",
    "            if postorder and inorder[-1] != stop:\n",
    "                cur = postorder.pop()\n",
    "                root = TreeNode(int(cur.split(\"_\")[0]))\n",
    "                root.right = helper(cur)\n",
    "                inorder.pop()\n",
    "                root.left = helper(stop)\n",
    "                return root\n",
    "            return None\n",
    "        \n",
    "        if data == \"^\":\n",
    "            return None \n",
    "        inorder, postorder = [item.split(\" \") for item in data.split(\"^\")]\n",
    "        return helper()\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return [None]\n",
    "        value = [root.val]\n",
    "        nodes = [root]\n",
    "        while nodes != []:\n",
    "            nodes0 = []\n",
    "            for node in nodes:\n",
    "                if node.left!=None:\n",
    "                    nodes0.append(node.left)\n",
    "                    value.append(node.left.val)\n",
    "                else:\n",
    "                    value.append(None)\n",
    "                if node.right!=None:\n",
    "                    nodes0.append(node.right)\n",
    "                    value.append(node.right.val)\n",
    "                else:\n",
    "                    value.append(None)\n",
    "            nodes = nodes0\n",
    "        # n = 0\n",
    "        # for i in range(len(nodes)-1,-1,-1):\n",
    "        #     if nodes[i] != None:\n",
    "        #         n = i\n",
    "        #         break\n",
    "        # nodes = nodes[:n+1]\n",
    "        return str(value)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data[0] == None:\n",
    "            return None\n",
    "        value = data[1:len(data)-1].split(\",\")\n",
    "        if value[0]=='None':\n",
    "            return None\n",
    "        head = TreeNode(int(value[0]))\n",
    "        nodes = [head]\n",
    "        index = 1\n",
    "        while nodes!=[]:\n",
    "            nodes0 = []\n",
    "            for node in nodes:\n",
    "                if value[index] == ' None':\n",
    "                    node.left = None\n",
    "                else:\n",
    "                    node.left = TreeNode(int(value[index]))\n",
    "                    nodes0.append(node.left)\n",
    "                index+=1\n",
    "                    \n",
    "                if value[index] == ' None':\n",
    "                    node.right = None\n",
    "                else:\n",
    "                    node.right = TreeNode(int(value[index]))\n",
    "                    nodes0.append(node.right)\n",
    "                index+=1\n",
    "            nodes = nodes0\n",
    "        return head\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def preorder(root):\n",
    "            if root is None:\n",
    "                res.append('None')\n",
    "            else:\n",
    "                res.append(str(root.val))\n",
    "                preorder(root.left)\n",
    "                preorder(root.right)\n",
    "        res = []\n",
    "        preorder(root)\n",
    "        return ','.join(res)\n",
    "            \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        l = data.split(',')\n",
    "        n = len(l)\n",
    "        if l[0] == 'None':\n",
    "            return\n",
    "        self.count = 1\n",
    "        self.res = TreeNode(int(l[0]))\n",
    "        def preorder(root):\n",
    "            if self.count >= n:\n",
    "                return\n",
    "            if l[self.count] != 'None':\n",
    "                root.left = TreeNode(int(l[self.count]))\n",
    "                self.count += 1\n",
    "                preorder(root.left)\n",
    "            else:\n",
    "                self.count += 1\n",
    "            if self.count >= n:\n",
    "                return\n",
    "            if l[self.count] != 'None':\n",
    "                root.right = TreeNode(int(l[self.count]))\n",
    "                self.count += 1\n",
    "                preorder(root.right)\n",
    "            else:\n",
    "                self.count += 1\n",
    "        preorder(self.res)\n",
    "        return self.res\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.root = root\n",
    "        return \"\"\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return self.root\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.root = root\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return self.root\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return root\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return data\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        ret = []\n",
    "        if not root:\n",
    "            return\n",
    "        ret = self.serializetool(root,ret)\n",
    "        return ret \n",
    "        \n",
    "    def serializetool(self,root,ret):\n",
    "        if not root:\n",
    "            ret.append(None)\n",
    "            return \n",
    "        ret.append((root.val))\n",
    "        root.left = self.serializetool(root.left,ret)\n",
    "        root.right = self.serializetool(root.right,ret)\n",
    "        return ret\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return []\n",
    "        if len(data)<=0:\n",
    "            return\n",
    "        value = data.pop(0)\n",
    "        root = None\n",
    "        if value != None:\n",
    "            root = TreeNode(value)\n",
    "            root.left = self.deserialize(data)\n",
    "            root.right = self.deserialize(data)\n",
    "        return root\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    curr_node = None\n",
    "    node_list = []\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        print(root)\n",
    "        return root\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return data\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# codec = Codec()\n",
    "# codec.deserialize(codec.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    s=None\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        Codec.s=root\n",
    "        return ' '       \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return Codec.s\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "global_root = None     \n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        global global_root\n",
    "        global_root = root\n",
    "        return \"\"\n",
    "        \n",
    "    def deserialize(self, data):\n",
    "        global global_root\n",
    "        return global_root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "\n",
    "        if not root:\n",
    "            return \"\"\n",
    "\n",
    "        l = []\n",
    "        q = [root]\n",
    "\n",
    "        while q:\n",
    "            p = q.pop(0)\n",
    "            l.append(str(p.val) if p else \"null\")\n",
    "\n",
    "            if p is not None:\n",
    "                q.append(p.left)\n",
    "                q.append(p.right)\n",
    "        \n",
    "        while l[-1] == \"null\":\n",
    "            l.pop()\n",
    "        \n",
    "        return \",\".join(l)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return None\n",
    "\n",
    "        return TreeNode(data)\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    # def serialize(self, root:TreeNode)->str:\n",
    "    #     s = ''\n",
    "    #     q = []\n",
    "    #     q.append(root)\n",
    "    #     while q:\n",
    "    #         root = q.pop(0)\n",
    "    #         if root:\n",
    "    #             s+=str(root.val)\n",
    "    #             q.append(root.left)\n",
    "    #             q.append(root.right)\n",
    "    #         else: s+='none'\n",
    "    #         s+=' '\n",
    "    #     return s\n",
    "    # def deserialize(self, data:str)->TreeNode:\n",
    "    #     tree = data.split()\n",
    "    #     if tree[0]=='none': return None\n",
    "    #     q = []\n",
    "    #     root = TreeNode(int(tree[0]))\n",
    "    #     q.append(root)\n",
    "    #     i=1\n",
    "    #     while q:\n",
    "    #         cur = q.pop(0)\n",
    "    #         if cur==None:continue\n",
    "    #         cur.left = TreeNode(int(tree[i])) if tree[i]!='none' else None\n",
    "    #         cur.right = TreeNode(int(tree[i+1])) if tree[i+1]!='none' else None\n",
    "    #         i+=2\n",
    "    #         q.append(cur.left)\n",
    "    #         q.append(cur.right)\n",
    "    #     return root\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        global a\n",
    "        a = root\n",
    "        return \" \"\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        global a \n",
    "        return a\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        global a\n",
    "        a = root\n",
    "        return \" \"\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        global a \n",
    "        return a\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return \"null,\"\n",
    "        root.left = self.serialize(root.left)\n",
    "        root.right = self.serialize(root.right)\n",
    "        return str(root.val)+\",\"+root.left+root.right\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def deseria(nodes):\n",
    "            if nodes == []:\n",
    "                return None\n",
    "            first = nodes.pop(0)\n",
    "            if first == \"null\":\n",
    "                return None\n",
    "            root = TreeNode(int(first))\n",
    "            root.left = deseria(nodes)\n",
    "            root.right = deseria(nodes)\n",
    "            return root\n",
    "        nodes = data.split(\",\")\n",
    "        root = deseria(nodes)\n",
    "        return root \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        global a\n",
    "        a = root\n",
    "        return \" \"\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        global a\n",
    "        return a\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# class Codec:\n",
    "\n",
    "#     def serialize(self, root):\n",
    "#         \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "#         :type root: TreeNode\n",
    "#         :rtype: str\n",
    "#         \"\"\"\n",
    "#         def func(root):\n",
    "#             if not root:arr.append('n')\n",
    "#             else:\n",
    "#                 arr.append(str(root.val))\n",
    "#                 func(root.left)\n",
    "#                 func(root.right)\n",
    "#         arr=[]\n",
    "#         func(root)\n",
    "#         #print(' '.join(arr))\n",
    "#         return ' '.join(arr)\n",
    "\n",
    "        \n",
    "\n",
    "#     def deserialize(self, data):\n",
    "#         \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "#         :type data: str\n",
    "#         :rtype: TreeNode\n",
    "#         \"\"\"\n",
    "#         def func(arr):\n",
    "#             v=arr.pop()\n",
    "#             if v=='n':return\n",
    "#             node=TreeNode(int(v))\n",
    "#             node.left=func(arr)\n",
    "#             node.right=func(arr)\n",
    "#             return node\n",
    "#         arr=list(data.split())\n",
    "#         arr.reverse()\n",
    "#         #print(arr)\n",
    "#         return func(arr)\n",
    "\n",
    "class Codec:\n",
    "    ans=None\n",
    "\n",
    "    def serialize(self, root):\n",
    "        Codec.ans=root\n",
    "        return ''\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        return Codec.ans\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \"#\"\n",
    "        root.left = self.serialize(root.left)\n",
    "        root.right = self.serialize(root.right)\n",
    "        return str(root.val)+\",\"+root.left+\",\"+root.right\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        lis = deque()\n",
    "        for i in data.split(','):\n",
    "            lis.append(i)\n",
    "        def dfs(li):\n",
    "            now = li.popleft()\n",
    "            if now==\"#\":\n",
    "                return None\n",
    "            print(now)\n",
    "            node = TreeNode(int(now))\n",
    "            node.left = dfs(li)\n",
    "            node.right=dfs(li)\n",
    "            return node\n",
    "        \n",
    "        return dfs(lis)\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    res = {}\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        tmp = id(root)\n",
    "        self.res[str(tmp)] = root\n",
    "        return str(tmp)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return self.res[data]\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    # def __init__(self):\n",
    "    #     self.haha = None\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        # print(root)\n",
    "        ans = []\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            p = q.popleft()\n",
    "            if p:\n",
    "                ans.append(str(p.val))\n",
    "            else:\n",
    "                ans.append('null')\n",
    "                continue\n",
    "            q.append(p.left)\n",
    "            q.append(p.right)\n",
    "\n",
    "        while ans:\n",
    "            if ans[-1] == 'null':\n",
    "                ans.pop()\n",
    "            else:\n",
    "                break\n",
    "        return \",\".join(ans)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return None\n",
    "        p = data.split(',')\n",
    "        ans = TreeNode()        \n",
    "        q = [(ans,0)]\n",
    "        while p:\n",
    "            snum = p.pop(0)\n",
    "            cur,f = q.pop(0)\n",
    "            if snum == 'null':\n",
    "                continue\n",
    "            if f == 0:            \n",
    "                cur.val = int(snum)\n",
    "                q.append((cur,1))\n",
    "                q.append((cur,2))\n",
    "            elif f == 1:\n",
    "                cur.left = TreeNode()\n",
    "                cur = cur.left\n",
    "                cur.val = int(snum)\n",
    "                q.append((cur,1))\n",
    "                q.append((cur,2))   \n",
    "            else:\n",
    "                cur.right = TreeNode()\n",
    "                cur = cur.right\n",
    "                cur.val = int(snum)\n",
    "                q.append((cur,1))\n",
    "                q.append((cur,2))             \n",
    "        return ans\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        # def dfs(root):\n",
    "        #     if not root:\n",
    "        #         return \"X\"\n",
    "        #     else:\n",
    "        #         return str(root.val) + \",\" + dfs(root.left) + \",\" + dfs(root.right)\n",
    "        # return dfs(root)\n",
    "        res = []\n",
    "        treelist = [root]\n",
    "        while treelist:\n",
    "            tree = treelist.pop(0)\n",
    "            if not tree:\n",
    "                res.append('X')\n",
    "            else:\n",
    "                res.append(str(tree.val))\n",
    "                treelist.append(tree.left)\n",
    "                treelist.append(tree.right)\n",
    "        return \",\".join(res)\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "\n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "\n",
    "        \"\"\"\n",
    "        def bfs(data):\n",
    "            print(data)\n",
    "            tree = TreeNode(data[0])\n",
    "            idx = 1\n",
    "            treelist = [tree]\n",
    "            while treelist:\n",
    "                pretree = treelist.pop(0)\n",
    "                leftval, rightval = data[idx], data[idx+1]\n",
    "                if leftval != \"X\":\n",
    "                    lefttree = TreeNode(leftval)\n",
    "                    pretree.left = lefttree\n",
    "                    treelist.append(lefttree)\n",
    "\n",
    "\n",
    "                if rightval != \"X\":\n",
    "                    righttree = TreeNode(rightval)\n",
    "                    pretree.right = righttree\n",
    "                    treelist.append(righttree)\n",
    "                idx += 2\n",
    "            return tree\n",
    "\n",
    "\n",
    "\n",
    "        if not data or data == \"X\":\n",
    "            return []\n",
    "        else:            \n",
    "            datalist = data.split(\",\")\n",
    "            return bfs(datalist)\n",
    "        \n",
    "\n",
    "        \n",
    "        #     if not len(data):\n",
    "        #         return\n",
    "        #     num = data.pop(0)\n",
    "        #     if num == \"X\":\n",
    "        #         return\n",
    "        #     else:\n",
    "        #         tree = TreeNode(int(num))\n",
    "        #         tree.left = dfs(data)\n",
    "        #         tree.right = dfs(data)\n",
    "        #         return tree\n",
    "\n",
    "        # if not data or data == \"X\":\n",
    "        #     return None\n",
    "        # else:\n",
    "        #     data = data.split(\",\")\n",
    "        #     return dfs(data)\n",
    "\n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "import collections\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.sb = []\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.serializeHelp(root,self.sb)\n",
    "        return ','.join(self.sb)\n",
    "    \n",
    "    def serializeHelp(self, root,sb):\n",
    "        if root == None:\n",
    "            sb.append('null')\n",
    "            return\n",
    "        \n",
    "        sb.append(str(root.val))\n",
    "        self.serializeHelp(root.left,sb)\n",
    "        self.serializeHelp(root.right,sb)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        nodes = data.split(',')\n",
    "        return self.deserializeHelp(collections.deque(nodes))\n",
    "    \n",
    "    def deserializeHelp(self,nodes):\n",
    "        if nodes == None:\n",
    "            return None\n",
    "        val = nodes.popleft()\n",
    "        if val == 'null':\n",
    "            return None\n",
    "        root = TreeNode(str(val))\n",
    "        root.left = self.deserializeHelp(nodes)\n",
    "        root.right = self.deserializeHelp(nodes)\n",
    "        return root\n",
    "\n",
    "# class Codec:\n",
    "\n",
    "#     def serialize(self, root):\n",
    "#         \"\"\"\n",
    "#         用一个list记录，最后转为string导出：前序遍历，空节点计作N，然后用,连接\n",
    "#         \"\"\"\n",
    "#         res = []\n",
    "#         def dfs(node):\n",
    "#             if not node:\n",
    "#                 res.append(\"N\")\n",
    "#                 return\n",
    "#             res.append(str(node.val))\n",
    "#             dfs(node.left)\n",
    "#             dfs(node.right)\n",
    "        \n",
    "#         dfs(root)\n",
    "#         return \",\".join(res)\n",
    "\n",
    "#     def deserialize(self, data):\n",
    "#         \"\"\"\n",
    "#         转化为list，然后用i遍历\n",
    "#         先确定根节点 root，然后遵循前序遍历的规则，递归生成左右子树\n",
    "#         \"\"\"\n",
    "#         vals = data.split(\",\")\n",
    "#         self.i = 0\n",
    "        \n",
    "#         def dfs():\n",
    "#             if vals[self.i] == \"N\":\n",
    "#                 self.i += 1\n",
    "#                 return None\n",
    "#             node = TreeNode(int(vals[self.i]))\n",
    "#             self.i += 1\n",
    "#             node.left = dfs()\n",
    "#             node.right = dfs()\n",
    "#             return node\n",
    "        \n",
    "#         return dfs()\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return \"#\"\n",
    "            l = helper(root.left)\n",
    "            r = helper(root.right)\n",
    "            return str(root.val) + \",\" + l + \",\" + r\n",
    "        # s = []\n",
    "        # print(helper(root))\n",
    "        return helper(root)\n",
    "            \n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def helper(s):\n",
    "            # print(s)\n",
    "            if s[0] == \"#\":\n",
    "                s.popleft()\n",
    "                return None\n",
    "            root = TreeNode(val = s[0])\n",
    "            s.popleft()\n",
    "            root.left = helper(s)\n",
    "            root.right = helper(s)\n",
    "            return root\n",
    "        s = data.split(\",\")\n",
    "        s = deque(s)\n",
    "        # print(s)\n",
    "        return helper(s)\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root: return \"null\"\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                res.append(str(node.val))\n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            else:\n",
    "                res.append(\"null\")\n",
    "        return  \",\".join(res)\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data == \"null\": return \n",
    "        vals, i = data.split(\",\"), 1\n",
    "        root = TreeNode(int(vals[0]))\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "\n",
    "        while(queue):\n",
    "            node = queue.popleft()\n",
    "            if vals[i] != \"null\":\n",
    "                node.left = TreeNode(int(vals[i]))\n",
    "                queue.append(node.left)\n",
    "            i += 1\n",
    "            if vals[i] != \"null\":\n",
    "                node.right = TreeNode(int(vals[i]))\n",
    "                queue.append(node.right)\n",
    "            i += 1\n",
    "        return root\n",
    "                \n",
    "\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import json \n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        pre_order = self.preorder(root)\n",
    "        return json.dumps(pre_order)\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        pre_order = json.loads(data)\n",
    "\n",
    "        def build_tree_by_pre_order():\n",
    "            nonlocal pre_order\n",
    "            if pre_order[0] is None:\n",
    "                pre_order = pre_order[1:]\n",
    "                return None \n",
    "            \n",
    "            root = TreeNode(pre_order[0])\n",
    "            pre_order = pre_order[1:]\n",
    "            root.left = build_tree_by_pre_order()\n",
    "            root.right = build_tree_by_pre_order()\n",
    "            return root\n",
    "\n",
    "\n",
    "        return build_tree_by_pre_order()\n",
    "\n",
    "        \n",
    "\n",
    "    def preorder(self, root):\n",
    "        if not root:\n",
    "            return [None]\n",
    "        return [root.val] + self.preorder(root.left) + self.preorder(root.right)\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "import collections\n",
    "\n",
    "## 前序遍历\n",
    "class Codec:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "\n",
    "    def preorder_tranverse(self, root):\n",
    "        if root is None:\n",
    "            self.res.append('null')\n",
    "            return\n",
    "        \n",
    "        self.res.append(str(root.val))\n",
    "        self.preorder_tranverse(root.left)\n",
    "        self.preorder_tranverse(root.right)\n",
    "    \n",
    "    def preorder_construct(self, nodes):\n",
    "        if len(nodes) == 0:\n",
    "            return None\n",
    "        \n",
    "        root = nodes.pop(0)\n",
    "        if root == 'null':\n",
    "            return None\n",
    "        \n",
    "        root = TreeNode(int(root))\n",
    "    \n",
    "        root.left = self.preorder_construct(nodes)\n",
    "        root.right = self.preorder_construct(nodes)\n",
    "\n",
    "        return root\n",
    "\n",
    "    def postorder_tranverse(self, root):\n",
    "        if root is None:\n",
    "            self.res.append('null')\n",
    "            return\n",
    "        \n",
    "        self.postorder_tranverse(root.left)\n",
    "        self.postorder_tranverse(root.right)\n",
    "        self.res.append(str(root.val))\n",
    "    \n",
    "    def postorder_construct(self, nodes):\n",
    "        if len(nodes) == 0:\n",
    "            return None\n",
    "        \n",
    "        root = nodes.pop(-1)\n",
    "        if root == 'null':\n",
    "            return None\n",
    "        \n",
    "        root = TreeNode(int(root))\n",
    "\n",
    "        root.right = self.postorder_construct(nodes)    \n",
    "        root.left = self.postorder_construct(nodes)\n",
    "        \n",
    "        return root\n",
    "\n",
    "    def levelorder_tranverse(self, root):\n",
    "        if root is None:\n",
    "            return []\n",
    "        \n",
    "        q = collections.deque()\n",
    "        q.append(root)\n",
    "\n",
    "        while q:\n",
    "            tmp = []\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if node is None:\n",
    "                    tmp.append('null')\n",
    "                    continue\n",
    "                tmp.append(str(node.val))\n",
    "\n",
    "                q.append(node.left)\n",
    "                q.append(node.right)\n",
    "            self.res.extend(tmp)\n",
    "        return self.res\n",
    "    \n",
    "    def levelorder_construct(self, nodes):\n",
    "        if len(nodes) == 0:\n",
    "            return None\n",
    "        print(nodes)\n",
    "        root = TreeNode(nodes[0])\n",
    "\n",
    "        q = collections.deque()\n",
    "        q.append(root)\n",
    "\n",
    "        index = 1\n",
    "\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                parent = q.popleft()\n",
    "                left = nodes[index]\n",
    "                index += 1\n",
    "                if left != 'null':\n",
    "                    parent.left = TreeNode(int(left))\n",
    "                    q.append(parent.left)\n",
    "\n",
    "                right = nodes[index]\n",
    "                index += 1\n",
    "                if right != 'null':\n",
    "                    parent.right = TreeNode(int(right))\n",
    "                    q.append(parent.right)\n",
    "        return root\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "\n",
    "        # self.preorder_tranverse(root)\n",
    "        # self.postorder_tranverse(root)\n",
    "        self.levelorder_tranverse(root)\n",
    "\n",
    "        res = ','.join(self.res)\n",
    "\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        \n",
    "        data = data.split(',')\n",
    "        if '' in data:\n",
    "            data.remove('')\n",
    "        # tree = self.preorder_construct(data)\n",
    "        # tree = self.postorder_construct(data)\n",
    "        tree = self.levelorder_construct(data)\n",
    "\n",
    "        return tree\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        self.serialized = ''\n",
    "\n",
    "        def preOrder(cur):\n",
    "            if not cur:\n",
    "                self.serialized += 'N '\n",
    "                return\n",
    "            self.serialized += str(cur.val) + ' '\n",
    "            preOrder(cur.left)\n",
    "            preOrder(cur.right)\n",
    "            return\n",
    "        \n",
    "        preOrder(root)\n",
    "        return self.serialized\n",
    "\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        data = data.split(\" \")\n",
    "        self.index = 0\n",
    "        def construct():\n",
    "            val = data[self.index]\n",
    "            curNode = None\n",
    "            self.index += 1\n",
    "\n",
    "            if val != \"N\":\n",
    "                curNode = TreeNode(int(val))\n",
    "            else:\n",
    "                return None\n",
    "            curNode.left = construct()\n",
    "            curNode.right = construct()\n",
    "            return curNode\n",
    "\n",
    "        res = construct()\n",
    "        print(res)\n",
    "        return res\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not root:return \"\"\n",
    "        out = \"\"\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if not node:\n",
    "                out += 'null,'\n",
    "                continue\n",
    "            out+=f'{node.val},'\n",
    "            q.append(node.left)\n",
    "            q.append(node.right)\n",
    "        return out[:-1]\n",
    "\n",
    "        \n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if data ==\"\": \n",
    "            return None\n",
    "        data = data.split(',')  # [\"1\",\"null\",\"null\"]\n",
    "        root = TreeNode()\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            s = data.pop(0)\n",
    "            if s == 'null':\n",
    "                continue\n",
    "            node.val = int(s)\n",
    "            node.left = TreeNode(val=1e5)\n",
    "            node.right = TreeNode(val=1e5)\n",
    "            q.append(node.left)\n",
    "            q.append(node.right)\n",
    "        def dps(node:TreeNode):\n",
    "            if node.left.val == 1e5:\n",
    "                node.left = None\n",
    "            else:\n",
    "                dps(node.left)\n",
    "            if node.right.val == 1e5:\n",
    "                node.right = None\n",
    "            else:\n",
    "                dps(node.right)\n",
    "        dps(root)\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return root\n",
    "            \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return \"\"\n",
    "            return \"(\" + str(node.val) + \")(\" + dfs(node.left) + \")(\" + dfs(node.right) + \")\"\n",
    "        return dfs(root)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        right_mark = [-1] * len(data)\n",
    "        stack = []\n",
    "        for i, c in enumerate(data):\n",
    "            if c == \"(\":\n",
    "                stack.append(i)\n",
    "            elif c == \")\":\n",
    "                right_mark[stack.pop(-1)] = i\n",
    "        def dfs(start, end):\n",
    "            if start == end:\n",
    "                return None\n",
    "            left_start = right_mark[start] + 1\n",
    "            right_start = right_mark[left_start] + 1\n",
    "            val = int(data[start + 1: left_start - 1])\n",
    "            node = TreeNode(val=val)\n",
    "            node.left = dfs(left_start + 1, right_start - 1)\n",
    "            node.right = dfs(right_start + 1, end - 1)\n",
    "            return node\n",
    "        \n",
    "        return dfs(0, len(data))\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "    \n",
    "    \n",
    "    res = []\n",
    "    SEP = ','\n",
    "    NONE = '#'\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "\n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def traverse(root):\n",
    "            if not root:\n",
    "                self.res.append(self.NONE)\n",
    "                return self.res\n",
    "\n",
    "            traverse(root.left)\n",
    "            traverse(root.right)\n",
    "            # 后序位置\n",
    "            self.res.append(str(root.val))\n",
    "\n",
    "            return self.res\n",
    "\n",
    "        traverse(root)\n",
    "        return self.SEP.join(self.res)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "\n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not data:\n",
    "            return None\n",
    "        nodeVals = collections.deque(data.split(self.SEP))\n",
    "\n",
    "        def traverse(nodeVals: collections.deque):\n",
    "            if not nodeVals:\n",
    "                return None\n",
    "            # 后序遍历列表最右侧就是根节点val\n",
    "            last = nodeVals.pop()\n",
    "            if last == self.NONE:\n",
    "                return None\n",
    "\n",
    "            root = TreeNode(int(last))\n",
    "\n",
    "            root.right = traverse(nodeVals)\n",
    "            root.left = traverse(nodeVals)\n",
    "\n",
    "            return root\n",
    "\n",
    "        return traverse(nodeVals)\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        return self.serializeHelper(root, \"\")\n",
    "\n",
    "    def serializeHelper(self, root, s):\n",
    "        if root is None:\n",
    "            s += \"None,\"\n",
    "            return s\n",
    "        s = self.serializeHelper(root.left, s)\n",
    "        s = self.serializeHelper(root.right, s)\n",
    "        s += str(root.val) + \",\"\n",
    "        \n",
    "        return s       \n",
    "        \n",
    "    def deserialize(self, data):\n",
    "        dataArray = data.split(\",\")\n",
    "        dataList = dataArray.copy()\n",
    "        dataList.pop()\n",
    "        return self.deserializeHelper(dataList)\n",
    "    \n",
    "    def deserializeHelper(self, dataList):\n",
    "        if dataList[-1] == \"None\":\n",
    "            dataList.pop()\n",
    "            return None\n",
    "        root = TreeNode(int(dataList[-1]))\n",
    "        dataList.pop()\n",
    "        root.right = self.deserializeHelper(dataList)\n",
    "        root.left = self.deserializeHelper(dataList)\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    # def __init__(self):\n",
    "    #     self.dict = dict()\n",
    "    #     self.res = []\n",
    "\n",
    "    def trace(self,root):\n",
    "        if not root:\n",
    "            return \"#\"\n",
    "        left_str = self.trace(root.left)\n",
    "        right_str = self.trace(root.right)\n",
    "        node_str = \"(\"+left_str+str(root.val)+right_str+\")\"\n",
    "        return node_str\n",
    "\n",
    "    def deal_str(self,data):\n",
    "        if not data:\n",
    "            return\n",
    "        print(data)\n",
    "        count = 0\n",
    "        left_str = []\n",
    "        for i in range(len(data)):\n",
    "            left_str.append(data[i])\n",
    "            if data[i] ==\"(\":\n",
    "                count+=1\n",
    "            elif data[i] ==\")\":\n",
    "                count-=1\n",
    "            elif count==1 and data[i]!='#':\n",
    "                index = i+1\n",
    "                while index <len(data) and data[index] not in [ '(',')','#'  ] :\n",
    "                    index+=1\n",
    "                print(data[i:index])\n",
    "                num = int(data[i:index])\n",
    "                \n",
    "                node = TreeNode(num)\n",
    "                node.left = self.deal_str(''.join(left_str[1:i]))\n",
    "                node.right = self.deal_str(data[index:-1])\n",
    "                return node\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "    \n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        \n",
    "        return self.trace(root)\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "    \n",
    "        return self.deal_str(data)\n",
    "        \n",
    "                \n",
    "        \n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root: Optional[TreeNode]) -> str:\n",
    "        if root is None:\n",
    "            return ''\n",
    "        left = self.serialize(root.left)\n",
    "        right = self.serialize(root.right)\n",
    "        if left == right == '':\n",
    "            return f'{root.val}'\n",
    "        else:\n",
    "            return f'{root.val}({left},{right})'\n",
    "\n",
    "    def deserialize(self, data: str) -> Optional[TreeNode]:\n",
    "        if data == '':\n",
    "            return None\n",
    "        left_bracket_pos = data.find('(')\n",
    "        if left_bracket_pos == -1:\n",
    "            return TreeNode(int(data))\n",
    "        v = TreeNode(int(data[:left_bracket_pos]))\n",
    "        stack = 0\n",
    "        dot_pos = -1\n",
    "        for i in range(left_bracket_pos+1, len(data)-1):\n",
    "            if data[i] == '(':\n",
    "                stack += 1\n",
    "            elif data[i] == ')':\n",
    "                stack -= 1\n",
    "            elif data[i] == ',' and stack == 0:\n",
    "                dot_pos = i\n",
    "                break\n",
    "\n",
    "        v.left = self.deserialize(data[left_bracket_pos+1:dot_pos])\n",
    "        v.right = self.deserialize(data[dot_pos+1:-1])\n",
    "        return v\n",
    "        \n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    def serialize(self, root):\n",
    "        \"\"\"Encodes a tree to a single string.\n",
    "        \n",
    "        :type root: TreeNode\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res = '('\n",
    "        def traversal(root) -> None:\n",
    "            nonlocal res\n",
    "            if root is None:\n",
    "                return\n",
    "            res += str(root.val)\n",
    "            res += '('\n",
    "            traversal(root.left)\n",
    "            res += ')'\n",
    "            res += '('\n",
    "            traversal(root.right)\n",
    "            res += ')'\n",
    "        traversal(root)\n",
    "        res += ')'\n",
    "        return res\n",
    "\n",
    "    def deserialize(self, data):\n",
    "        \"\"\"Decodes your encoded data to tree.\n",
    "        \n",
    "        :type data: str\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        def construct(s) -> Optional[TreeNode]:\n",
    "            if s is None:\n",
    "                return\n",
    "            if s == '()':\n",
    "                return\n",
    "            flag = None\n",
    "            for i in range(1, len(s)):\n",
    "                if s[i] == '(':\n",
    "                    flag = i\n",
    "                    break\n",
    "            root = TreeNode(int(s[1: i]))\n",
    "            left, right = None, None\n",
    "            stack = []\n",
    "            for i in range(flag, len(s)):\n",
    "                if s[i] == '(':\n",
    "                    stack.append(s[i])\n",
    "                elif s[i] == ')':\n",
    "                    stack.pop()\n",
    "                    if len(stack) == 0:\n",
    "                        left = s[flag: i + 1]\n",
    "                        right = s[i + 1: -1]\n",
    "                        break\n",
    "            root.left = construct(left)\n",
    "            root.right = construct(right)\n",
    "            return root\n",
    "        return construct(data)\n",
    "\n",
    "# Your Codec object will be instantiated and called as such:\n",
    "# ser = Codec()\n",
    "# deser = Codec()\n",
    "# ans = deser.deserialize(ser.serialize(root))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
